{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d47b3333",
   "metadata": {},
   "source": [
    "## DAY 20"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAn4AAACCCAIAAABXfVJ8AAAAAXNSR0IArs4c6QAAIABJREFUeAHtnQdYFEka98Gwu3reGjYHrQkwTAAkBwEBEQUEJKOCOeesZAwoSs45Sk7DkJkZmESGubtvv3Pd3bu923S7t+E26K5pVeb7qntmmIEhiKwKVj8+0l1d4a1/Vfev36rqaTWANqQAUgApgBRACiAFnqICak+xLFQUUgApgBRACiAFkAIAoRd1AqQAUgApgBRACjxVBRB6n6rcqDCkAFIAKYAUQAog9KI+gBRACiAFkAJIgaeqAELvU5UbFYYUQAogBZACSAGEXtQHkAJIAaQAUgAp8FQVQOh9qnKjwpACSAGkAFIAKYDQi/oAUgApgBRACiAFnqoCCL1PVW5UGFIAKYAUQAogBRB6UR9ACiAFkAJIAaTAU1UAofepyo0KQwogBZACSAGkAEIv6gNIAaQAUgApgBR4qgog9D5VuVFhSAGkAFIAKYAUQOhFfQApgBRACiAFkAJPVQGE3qcqNyoMKYAUQAogBZACCL2oD9hUisRisbgj//DjaGFUIICpmrP8HifVcxh3dxush7gkRGrbpqxmLKDWdjRjdT2Km/k9Qm74TqvRoqBwpABSACkwhgIIvWOI8yxOrfHF7vvwP1bi6VEsMMxu7cWjdVWcHyXOxINnOHppa8J6BqBa3exrNBWqPD56d1zpx9TnZB9Rkd9jB2m4+O6KzCjkd/ZhZor7Ojqq8hN3+aylEB87L5QAKYAUmBYKIPQ+Z82kgF6xqM5WS4V5epvO9OHgFYsRelUIpBhE0DjPlD6miMU9Ub4jBX189ALKuZTCsmuZjiMzUyx6IvsUnQtZ9bLGFA/ATX4krow9qk0hTCQbFAcpgBSYXgog9D5n7SVDb08vxGtWmPdI+0KyG+H4sKBDjNA7Uh3lEJKFA+6hCkVCsVjcXhFNUY4AwCTQOzyLyR7To1gdMk+Xe9TLmIJtazaeEUmfrQYq445PNnOUDimAFHh+FUDofc7aRobeitZ2sVgsqM8ebh/Fu7lrQNzVmo05S8jrHa6P8rHDtjjoRfY1XI5IFovF/Z1txnRN5SjPDL3GLmfwIWZOaZSpLknRKhLVIrcRzsAP9PIP2SueQftIAaTATFAAofc5a0UZejcfjxMNiMV9or3mihYSXCKKxGJxa8HlqyzIFEX0kg3tToZF1zS392Oe1EBfT11p5jYXM/mQ5bEC6CiLRRVe1p75LL5YLGZGrwZg+Fwv1cid2wN9RW5F0gqytPQ1Gw8Wsrh4zvymytObt6pcZrVmw4H0ohrcZRcPDAhaasNP7dXRxLlCPFKILc3iF5nJ66S3jYt5eKyYdbKw5WkcaGZFxEYAgG18HTwQN24ytruQVtyDDR5385svn9osiz/GX+3Yum6xWMzJ3KNptZMH69SXuX2FcoJJoHc/fCwSi/MDpDltz23FApjOK11j8qp6MSM72+qC9rorl6V4RD1f1QVT9fM2W2srnsD3NVYfFWL5NOacxeXbsC8BK0W8xs7x7JUMYTesT3+XICH8sJ4SuIGV286Ua3XdvViE7s7yjKsuxvSRRaAQpABS4FkpgND7rJQfpVwZej0dLWNrOsVicee1wzL8AYKGVjm3UyzuC9vpkwvRqYRe54B0GF/AraquqmLWd2D47OviWGlr4IXJ0FtVUIklFovrE+2HoZfCsMhqhTDs5le7y8BrvSsKEgw6YZ0cDpsn7BT3djRjHFdc4ewblAZv9mJxX5eAw2bzhRhaxGJe6eXl2JylsfNljLPde9ZK62R7Og1LIe5mZzGwZwSSmTO24Fq8x3WlAnrZrFpBX5eIzeZ0467iQNcVH71RRJQG0132Q7MHeo+aGwIALlVjFnPSlssFhRGnEL2NbE5nt4jP5rRJV0z1C084qcAqLFbflYfVvKMkcLRaZDdBATu5pVSsAeXoreHw+7qhFB34+jGxOCXQR56Jtf8JfLi6vaWuoqKSK8IALmI66D/51LS8ELSDFEAKPJECCL1PJN/UJ1ZAr9eeq9jNucfaSOrU0EzPdQ+IxYKKlcAYdyAVvV7nM4mJJzbITTLeeBrzfvvTt0LwAACk6BWLB/q6Yg+7AYLexQALJfQSCDujmbDQgYENq41kWRFZfHgz7+JU6cqCjsTV4MiUo5egfVCA3fLZ5TGyWMDvUjkeLXKzKwCAamDW0QuNunjIE49zKb9Z3NfXKxb394hMl8MwKzd/LInQAStf5vWKO1hpUnRY7W/DCupoSFa1YlleONgbXgqfA7o5xjow0G1zEm6Ml70is6cQvWJ+6QXpcLZdUAf2GFKXGjxkkMIewWETbkxZiLNCsNJuxDW2WCzuFdTTsQcXOXoHulnrsBqQKYZsbFq4syFDmpLq1YA9JXVVhuPi0MzsYJ8Ri4tCtirljg6QAkiBZ6cAQu+z015lyQroJem4NmKMidlgg8WlhFf3iMXiwlN+QBV6yZqa8rFlLL59NXSbxbVRxnhRcvSeP+CkUPjQgLPfyRRIxoHe5N02Q0OYm5IwK7pCPDCCYSlJdLs6zJuSoZd8qgh60v3tVea0oXdiiJpmZZgPKyzDXoIi6hS2QTLUJkpXD9W09/Y05GSxxeL+3k1m+gAAz1P5kDe1EbirLkNv3z7noSHToKwmsVjcI6xdPpYjp1fIgSa25x3H66Jp7YFVRFwc6qFQ/SlEb6+bxdAqrtRaKEh7daJCWUO7pu47cPSm+64dClXeOxtTCx8dOlrpWtBPl6P3kKv8fWLCwRTsUUlQiyf1C06FSUQtRkNvJhH8MrkwsFGGZ+VS0BFSACnw9BVA6H36mo9ZogJ6AQBbEjDGNMYbAMCwcMIGcHt87bRVohcADWf/fRcvRV+rqOZweL34xOxI9PY2uTMUbZCit7sul93RJxYPVCUf0RgCL/BKgr6XmF8BwTi0UeLgOmv5T2osv4YNbLbkDn8X2T8dG9zml5nCtIR1URAVvU3Y8jG9wx394tLzu3wv1YjFA/n74CxsSJlQLO5L2yj11GXobVw/VDQ4cr4SZtLJ1leqiEIMAIz8IiDk+zsD4bg1vjGi6+CzS397ocVQBacQvUw5EgEAVwrhBLCwMVNWutJf4lo/HL3Vl1yUTigcXC6Dv/bRzWPSMFdajt41lvLRB+B+oQTm09WCAzwkCU6N94jYF86fk28XqrGx7U7mGoXM0S5SACnwDBVA6H2G4qsqWhm9htZbsRt0325XHfcjeXDmj3kJmzxUMeAcmAIHgQf6+7jN9SWF2SkJuULMyxvu9YoqrJVKlqK3T8DDXN6umO22Q34rACHlWC7cYqVEgBSFLbGWer004+ZuGK0x/YRyNGAQCV03cUfNavyEwRFhv1jcx93FALbRDWKx+OBGC+t1xyFjykM1NZ1qu8QDPUJbHSoefQz09nVxDUaZSAUAROTDp5ZRtv7TftKRgCmd61WB3o7mEWvU8YrprWvBRqR76hNHeX7QqcAG1nnMFPzl3rHQ28PxwrK9UoQ9J6msdidrVP8aNwn9jxRACjwtBRB6n5bSEyxHGb2AaJCPvflZFnE2hwsnac/Z4cwYgV7Nk3BF9EDnWVf5wKxdFbauaILo7cg/HJoLWTjQK/IzGfKrNiRj63kFVUNLpQEARLMi+KKs3OvVw71ebnGQ8qA38dg1aMRA85DzV4aNA6edXFfYMSDuZ6/XBqQVazEMNazzO9YnFne1VTBkbwBNFr1azSKY5UB/37ANm/cUMxNPyRrkj/V6R0UvAKfxNeJi8YmNQyu+ZVYRDI/ia9YG8gKlbxdNBL3BidDrFbVcIys+PckyRX+RAkiB50QBhN7npCFkZgxDLwC0LVl9cBUSXK/c191qrI3fU0egN6AYkrC9XA5eDae9XRhnJo5eMs3mGvauT38XZ80KaU7kHdkYF/tjDwy9YWrmtAULlKOX4JvYAg3oExx1HJrvJJmsgT6uWFwdObTGJzwd+svNLJhtV1kIHPolGBZCkA/kFF8Ti8UNGYfl/J4ceqkH83CbL+wwNDRQ/GeZ1QQnwAeE8p9ofmbo1bf2wl7/EfcIGnasGhINAEBzPMjHFqj3cEoYsrHxiaDX6wx8j3mgu91Vcc5A1rnQX6QAUuA5UQCh9zlpCJkZI9ALgEG9AFvRJBbXJWyQ3YdHoNclCk5jinsLLh1fZWXpu+N4eRP2Eu3Iud5RBpzxzyfo2W7hYAPM/NpkG+lwrn4ltjaqt6MtMuTE1s2bj5w+38Dr7sOiyZZZAUC3reXB2dVuftP5oKNbN2/ee/hMYR02y9jH8bIYGhq2PBwFGd0HYZu6ZRVe89VXGwbE4q6eHrG4M1zhwwWTQS95eS5W9V5OoXTGWKYuAMDscA5O5ZRjdljwM0MvIGg4H0vHlx/393QUp8ZfvXzlSmRUZgETWwYuFve2n/S0kNs+EfQCbduyNthb+vl1F08eWGdvbW23es/RoOyK5h0eSm+Iy7NFO0gBpMDTV+Ax0Lts2bJ33333tdde+/Of/zwfbcoKLFiwYPHixW+//fayZcueqBVVoBecxCdxe7g+smFYVcusNLOwJbWQv9hWnZL4uAPOuOVr9l7El2jVpobj05BOm4PbOnEvF897oDI1duRPalh67GPB146Vth5ew2EPAyVNtDe0Yo8J/z+e80rpez5aK87gEOrjDb3CpPBer4plVqPN9epZeeIWlEfsUipXerCiDvPE26uSSNC5fnboxezxOxrZKoCPLMrbgLCxZLfbEHcVVzirWGYlm+sFAKx0OVjPlz6rDeU50LPVRf62mCpVUBhSACnwFBWYKHqXLl26ZMmSuXPnqqurq6FNlQLq6upz5sx59dVX33///cm3oI0rC9vW2WErgvGMbA9UslglaWEK2RrElMJ4lUmKv/FLOxOTjaWujTrmTQaWqRXwKCNQSr6dMdhxebLy7zlZJJfDaOXR22X5a+yLLsLyYV09Iv2RKYq5Q2JuGQysqQjd7QKAfjRmQF6k4os6AJDpe4Piq6thRGZ1xZXAPSpf/wnNqMLyzzORvZlL0tQqqKhlsViF8WdkZsC/FqFZWMwcxSVCO46nwPwrry2XD68rpLHen4AlYW1xVdBQIcKp2HwWi1VbeU2bRARgE17VBNknE90v52HJM5S4p5AcgM3FWIzoA9JQn6swQxYrXXHO9mxMAVQ1L1IpqcoDMn3XyUtlFZhqtczSgqzDG+1HztWu9w/DSmFZmw4tzHI8gVW2ulDx7WCSlvbpy+k1TKhnbXVlekyEhbbKdlBpDQpECiAF/nAFJoTe999/f+HChbNmzVJFHBSmpIC6uvqf/vSn99577w9vOlQAUgApgBRACkxPBSaE3sWLFyPuKgF2zAN1dfUn9X2nZ2dCViMFkAJIAaTARBQYH73vvvvuyy+/rMia2bNnv4w2ZQXmzJkzTKI333xzIg2A4iAFkAJIAaTAi6bA+OhdsmTJ7Nmz5VxZuHDh9u3bW1paetAmU4DH44WEhLz77ruKYwOvvvrqi9aZUH2RAkgBpABSYCIKjI/e+fPnKy6t2rp16zfffCNBm7IC9+/fDwwMXLhwofwZZe7cuRNpABQHKYAUQAogBV40BcZH77DRZhaL9fvvvytzBx1BBf72t7+RyWQ5etXV1V+0zoTqixRACiAFkAITUWB89L700ktynKipqQmFwsHBQQTbkQp88cUXWlpailpNpAFQHKQAUgApgBR40RR4bPSKRCKE3pHclUgkX375JZVKfaHQq6en+OHbF+3aGb++NJrsteXx46IYSAGkwAukAEKvSoxOJvAFRO+mTZteoGvl8atqba38jajHzwGlQAogBWakAgi9k6GsyjQIvTPyCnmSSiH0Pol6KC1SYAYrgNCrEqOTCUToncHXyeSqNgn0GtPfj3J8Z/ziSEsvOr+Ff/9hrMhYtKEPTo0WlbTsgvOba0Y7Kw8nLbvg8qaD/KtS8nC0gxRACjymAgi9k6GsyjTPCXp19Bx9HZ/SD+VPbsDZfJWjh7ubjenMnyeeBHpTd8yXxMwp0h/nOj7oskgSN+tD1/fJY0bcu26xJE79E7f3NcaMttNhiSRO/d8e40TbumbJo6tzP/d8f+grHmNmi04iBZACoykwlegdHBy8d+/eb6Nv9+7dm9wSrXFzvnv37iRyvnPnzujG/vbgwQOViB0t8MnRG5BSU3zpiLSpSNQEZuspx9EaDgv3iuSL5FvngLg/Ysd6e9dkbtJTmoJ9XPQSiOT9CbU8dlNdbQNPwL/kozfyIwGKFabQdPwiirJ3SG/1JA39kOxGoaijvbHIzYCqEJNgaO3Z0NbZIerIjTxAwz6seCC2pLe7C6oj5O83NQDAmymXqqN7oLPBSSE9vmt0JLGfk4/tE07ltPR0dcIUAs5mLWiAy87T/X3deB5XdnqOSK0i4HHRS6G8+78oNUmc2p3QJfpjOJeEZR+EzpHEqT28Os9+DAwSlv01BEZ7FD3PaYyvJxCWDQTBaJK4V9YrijqsQoRlfYFzvj392p3oV7xUrR4j0Uxq2lrXWcFPO2hQdf3OlyS6DX3zQnfl5vJmnkjU0V6bSAeAoEHbe6mgq6Ojt73JfZU+IJun17Y464z9hDDMIHSIFJjGCkwleu/cuZOSkrJhlG3Tpk2XLl369ttvR0PXGOHffvttVFTUpk2bVObt5+cXFRV1586dMXIYeerhw4dnzpzZuHGjyjx37tzJ5/NHphoj5MnRq2G1h9/Z6IJ1J5djMU05wWOTCZA0abJtXXgFN++4BhE8n+il2nhlFlY0NzZ218cbwK+4E6gm9sL+bhuTUdGx6WQsXyhsa+vOkaHXLaK8MXW7Np3mduQytypu6LIjr6rsFPiZGtIZ2iFFrWnYA0toZv2ZvZ64PGQCAQASVaaVX0hqdfzJYWgjkjVrOSIZejWjKni7NjhiKaj4N5I3Hkgojj2E56FJln03ecgIFXsTR6+exrLztm//n4C5GALVJLHq/ZveDDFcaq1sJYME9pi8yzmwYBCSUk0Sp/7l3tdjzd53UHZ+aUSw2+Rd9n55NLWv9r0WZ/6+k3I0Khatdd+fH0lzU/vPgdfiV7zvrByNQgS7jN9t2QujfX3ozYM+f/764GsJFu+5KkfbFMtM3AA/3eSy8TJPIGTzB1Jk6CUSXdlttZ5W2jQaXUdXmwDAlrMZzJQgBp2m43pR0JJnBoCBrWcvJ3W5ChVREFJgBiowlei9deuWv7+/+ujbG2+8ERUV9csvv4wBsJGnbt68GRcX984774yW8UsvveTi4nLz5s2RaccIefDgwfLly2fPnq0y28WLF+fl5Y2RfOSpJ0cvAODg1RpW+hEygVLUwj+8Hg7JbglN2miGf/XPIDQhVl+HAkZsOiYewh62oyH0WSB6U/wPBV9OSkoK2OuNx3XyPxKXkJQYH+NjCR0LA3uPSwGHfY6GJyQmRZzcKvM1qIeCryQlJYWf3XspJt7WbOjj9iMKlAZM0OvVXH+E01K1b6PHenevdebyGzbpYvUAu7EmJmiPzAClclbYOtlbGJwoFMrQu6KI2y693Ws6sXgtQzOddMfmrjZ9Ksxmz8XKvHM+AIDLBa2HNtkq5Sg90CtubthkpuzfERmnspqDfS/zpF4vNaVeuMlZ6dvyW4/m5YTDnCe+TQy9y66Hz5YSV4ZAhUP1f+96G9en9OArCuE4euX/q98MWqSLcbrwwLwxov0assgAe6DL3TdGNLXb4QtNsGiZe5SifX3oTSJh2e5Vb8Ste63v0IK75xeuwB9C9OxbBa16dHhgaOrgZGMSVNIhQy9xZzbvsq+Nom7x1bxTPlLfObeFv2cdAGTd3LY+ZysEX0Wd0P6MVWCK0evn56f4YuuwfXV1dTKZzGQy7927NxJdKkMePHhQXV2tpaWl+GOWw7KdO3eus7PzJNCrq6ur+KvLitkuWrTomaBXz9Zb0NW+LaKqJeMUfk8LqxafWW2JdUDL6t6uFYYjBvtoRpGVnIhNUk7YuyZ3ceqCD27133maLWjbgs0apqUl7t2yae/pK32iCnMtYLnhUE8nJ/7k3g1+u4paBBd3mgGiRlBOfWnSRX/fTafOpXf3iz3tlb9vr+oSmBh6Na+WtwdtUlzrs72pMRPPj2G6OuFaU9JJV1XZw7Ah9Op4sfl18mgZLcLT8gNA9D4Rzy1POBkaXVed7YA9MwTF51dXVze18uryIvW05HAn2BzNq7q8eygptue4O4RTHEwjH5Kil0CNzCmprq5u4fAr0sKo8LO+wHd/XHV1dW0Tj12Zsdpk/OcSAMDE0AtCPBb+HiuHqNLOvfPzAmUT927Wr/8Spa4Sq4+uzC2zl877uli98cvVUaJdnVu55j1cCyeLN34ePRpz7Xv4cMTaFW8qRoPoxRQz1n6v/+T8Osf38CdBs3W+gppYxVHtwCH0GpV0DyQUltfWMFu4vKQgf00iKOOyN8s6clxF25lt8C0s25jmZP9Vw5oGHSIFZqQCTxW9ampqs2bNMjIyEolEKkE7LPDBgwcffPCBiYnJaIDEYTmT0Asd39RWsbjXy84Y73DjotfvWFJDQRhRNjJp75rcURKI3x/357ETNsNsqIzlKyytbF29Onv7HSwgevm1aXj+ewMLcy7u1aBpt3W0OuIuB1W/oaN36tCrlVIn2OwsrQ5W6BB6AQCrtp1qyryAGzPy/yH0Wmzi82rlETKahSdlB0Qt07Q6UX5MyNGTIRX17PPbFLxV0vJIZkfRCan7S9DULRd0eqxWeqowWH+opb4Aw4YMvbKcAdk4rk6Uu0dxRRjhUHxVXeIheZQxdiaIXgDAKddFD0e4vL9fnHdWyVJgY/rmnWglNsOp3KtzSuzfVzTD0vjN37A5Y0VOP4qaU7FGKZqp4Vu3RkQbjJpT46AUzVD/bTnLpeglLROfmcdyGoq2xjOoNUfeINCWIfTqWvHF4uTDcAE1zcyR39NpbcCo4bdukvVYOXrB5sziwKHpYcUaoX2kwAxT4GmjV01Nbfbs2a6urt9///24C6M+++yzNWvWzJ07V9EfHbk/w9BruOJYHy/PQHZjGge9Dgf47VW2JFlsfMBZtsxqU1ZzzhkArI+2dfW1MMuvXo3r7RvA0cu+dhXvyjtOZ1bEnKLQdQTca1JkUfUbRFOIXuB8sbQxS8FHBUro3RVcUBZ1dLTragi9wLWxky3zlFaWclrlS9AcNp7iFkfizpyu+15BfZZibvQ9ecJ86eK15UbbutnZekNqwYjJrO6B/t5uuPUODPSLGgsVk1ueKBJm7VAMAe7hwlqFmWalc0oHE0cvgbj0qxHo/burireMWs4MR+9PB5coVwja0HByuOP786HFI6Mxj89SxLMkTu2XI4tGRqs8Ih0Sl6KX/vY3xxbij3d4hdd6h4+KXmBaPTBgvxJ33g3yeL2HTPXzW/gHZC8zpdbz9rtiZSL0KnUfdDCTFXgG6FVTU1uwYMGePXu+/vrrYW6u4uG33357+PBhxe8VjoTujPR6Dc2P9PLy5G+XHC/qLToBV+Pq2Xr0jRhwTq9uC9uh9JNJisuscPQeSGooPOILANAx9erpF6tEL4nKaBV1bsYGmelmHqLeganzegEg6p6JLeKzG1PCt5hvC/NZeaapMdN1d5AbFUQVspqK400YirdxpetNAb3kYwWcvP0WAAAL3zOcqkR5PBuvfZ3sMi0NmInL3sh2ZrL8FCDqXqgWZu1eiYc4XKwtPQ1zUNz0jM1WmK/A/gUI2orNTQyHzpIMo1iCFF/doRBA2BdbUXVln0LIqLsTRy+d8Z58rZOchd/tfn141oSl/xzh9Q6GvrpiWDzCshtXhqN3MOzV4TUnLPvg0shof7YakdvABSmhfwtehM3ML/3i7AKpplhkEycfQW38KAPOJM/klmshsAdSTda2dYnM9CinY6pyQrfApOY7uY25BtgCAIfY5ngvldPzwwxCh0iBaa/As0Gvmpra4sWLo6Ojb926pYhb+f6vv/4aFRX11ltvjYZbxfCZ5vUqoxes3MhqE9VVVhRlFtQroZfke76sr4dfprDt9LYbiV7GuqPNXE5VaVnRtfyeUbxeAIhueyJaOOyK8oqKojxud99Uohe7TLS09Qx0tYxcdjc2tnX19LTVF6ymAT193bHXCiugF+gae5ZzhDWVFU21pX5rjQGBElPN27neAmjqHYnI4bc1VzGb2KySzY4mAID0ivqaijJmXUtR/Bm6Fl6Ibmpz135d+PYL3Ai6We19nraKQ7qyAWeqTnldU3V5WV1DS86VI2RsUOFASiWrsqy8prkm54q1sfIqLWmOw/9MHL22hm/jxP35zJ9K/RfeugpR9yhwkfwJDM+aQn0fnxW+e35e7cZF/7mAvRQUPf+U8qOLptb7t6MhU++dn8fasOir83i0eQHK0TQoS3/GJo/vXXiFtWHRl3i0mHkhytHImku/j4S53b/4St2GxZ+Hz+va+tpnYQvOKUbTtm3gt+ox5GvoFAacASBQVqWXN9UzK+sbGi7sXkcCgGrplFPZUldVyWE37HM1hbXTXF7IG3BfiZZZDe9F6HhGKvDM0Kuurk6hUCorK0e+FHT//v3KykoKhTL2FK+cvjMMvc+8nxHpBi2dPetXjb+SaGLLrIZXyMR9f05m7FgvpA5PofqYoKXd0F5jN76ZqpMT9S06u5nDVjqrjjrZ0Imj10Tn3Q9PvVK59j0drCxN0rLiXQv+tv31YZXT0Fzad/KV1g1v2WDYIxJAnO+i68cWblQeIyZrLO08/gp741u2WDQCAcT4wGh+I6IJjs3jbHpztQyiV70WXz+2cItyNBJ5WduReVy/N9fIol32XHz92KvblKN5hF1L37NaOewxhDNet72j9pKOrIjHSImiIgWmoQLPDL04OJcvX97d3S13diUSyaNHjz744AMDAwM5WcfdQeidko5H1tAgY5uZf0xvZ4n52N4oVuTk0Dsl1sLRS23zhrQJDfyqLNHQwomTjC1CU3l6KgInjt6pKO0Z50GgaJew29bbDHtamJhVGpbYvgNTAAAgAElEQVT59U2W8rWCE0uEYiEFpq8Czxi9c+bM8fLy+vTTT/ElV48ePfr444+9vLxefvnlcYkrj4DQOxX9TyMwvYLXzufx+M2V6bYTG1B9tuidilr/sXm8UOj9Y6VEuSMFZpYCzxi9ampq8+fP37Fjx/fffy+RSL799tuDBw/OmTNHjtWJ7CD0Pqs+idA7tvIIvWPrg84iBV5YBZ49etXV1RcuXHj58uWvv/46MjLyjTfemAhuFeMg9L6w3RdVHCmAFEAKTEcFnj16cYiSSKQtW7aQyeQxfrVKEbeK+wi907HnIZuRAkgBpMALq8Dzgl51dfW5c+dOcEmzInfV1NQQel/Y7osqjhRACiAFpqMCTw+96urqr7zyyuPO4+KUnT179ssvvzyaQ4zQOx17HrIZKYAUQAq8sAo8PfS+9NJLlpaW4/4g8zCPFv/ZZxMTEwsLi9F+URKh94XtvqjiSAGkAFJgOirw9ND7yiuvHD58uKKiQlNTczT/dSR31dTUNDU1S0pKjh079tJLL6mMgNA7HXseshkpgBRACrywCjxV9J46der27dvnz59/7bXXVEJ0ZOD8+fMjIiJu374dGBg4CfT++OOPn3766T9VbR9//DGVSh1tdvnVV1+NjIxUlQ6GffHFF3fv3lX8JRCJRDIl3+t9YTsiqjhSACmAFHhxFHja6B0cHPzuu+8m+F2E+fPn7969+5tvvhkcHJwEeh8+fFhXV6etrb148eKFqrbRuKumpqaurj5v3jxViRa+9dZb27dv/+yzzxB6X5zrBNUUKYAUQApMoQLPAL2Dg4Mff/yxs7PzaHO3uO87a9YsV1fXr7766tGjRxKJZBLolUgkt2/fzs7OBgCM9KcnFzJr1qy1a9eKxeKRXzxEXu8U9kuUFVIAKYAUmMEKPAP0SiSSBw8e9Pb2mpubj+Z3zpo1y9TUlM/nyz3LyaEXp29ycvI777zzWBPMKsE8d+7clStXCgSChw8fyg2T7yD0zuDrBFUNKYAUQApMoQLPBr0SieThw4eVlZVLly5VCbl33323urr6wYMHcrBNGr0SieTmzZsXL16cP3++yrImHqijo9Pf34974XLD5DsIvVPYL1FWSAGkAFJgBivwzNCLEzEyMvKdd95RhJ+6uvrrr78eGRn5yy+/yKk26QFnPIfBwcFvvvnm7NmzCxYsUCxr4vuzZ8/W1tauqqq6d++eolWK+wi9M/g6QVVDCiAFkAJTqMCzRK9EIvnhhx+OHDkye/ZsOQVfeeWV/fv3//e//1Wk2hOiF8/q888/3759+5/+9Cd5WRPfoVAohYWFY3B3Klc4k6gHzgZttYHfe8e30Mz6Y9udAdDPbe+xNH3uviWez+Ydlpk65X/pxlY9/d32ZloTzdlsVUhI0BZLpegaa/yCQ45bK4WpPDjUyoxReQIAcCipPjPQZbSzkw03PH58nwHJqozd+rg5hJZxAh43zZjxw6rFCWvGEimW2XJgzByek5Omrlv5rFSKsjWuwdlFx7Yrh03oyNDGv6mdV1mfO5Y0E8rpBYpk5bK7m1elO+Gr9gmlqW4XbvnDmodmvvrEoan/uugzRq9EIrlx44a7uzv+4tDLL7+8fv36f/7znyMHdZ9kwBlH7+Dg4Geffebv7z9v3ryJQ1ddXf3tt99OT0//7bffhj0NDDucKq+XYeQsqi1qLAqS99tph17PSxXRq5Tp94TXFkxull5RPX42ztvFA+LOymBN+UfbCRpXSzkD/S1+4yd+uuglaGxLbLi0ZxUAMxa9G/enJZ95jOeV5Oq6DVbjtxMAYNPB9KTTziqjTi16vS9VVkbYqyzocQM3H8mMO7nuMVJtDiuJ2vUY8ceLejC9/KzreJGm4fk/FL0A0EIyWSet5PfjqRHo2aP34cOHN27c0NHRUVdX19XV7e/vH4Y0/PDJ0Yvnc+PGDVdXV0U/e2wML1iwICsr6+bNmyqtUgycKvRaB5VlbKdnNjRvXSn9Wv0o6CVo0RlaZGkcIoVG1yIDAEiaVIY23KgUDayPEKh0BplEhPsEIkObQZIzCQZp0ulaZAr1/w+nM+hU2afKCVo0ujRE2s2GQgh4cgKRSofl0Kmaw7xeEoW2J0eY7OqgTadiZZLpDBgT5i/NDftDINK1tUlYkSQNKoOuhWVMpjNogECgMxhaWlRtBp2M2UwkAC362kouG5aoBatM0tDCqsnQxKsmz9l5e6dAwBsQO6yQfrOdom3F4xSyBa04emFCzBwtTVw6DTqdqkmlazPoRIIUvQQCmaHN0IA5EzS1aLjxR5NlXi+BRKXhhdPJUA4ijcHAtdagUOlamnj16AwaCRBpdDqBrInXnyzTFzdW09Cyq6fGHF7RcvQSaHQG3nBEDQq0k8GgaBABINIZDLJMPiqdoUEmYl4vCdOWQdXEywcEkoZMbZqsNFnbMeh4DmQKjapJoTMY/7/tYA+QVTB8hNdLlmtFho0Ty2w5RNTAa46JA+uhQcH7G4OmJbVBi06nkCmwB9LoBwJLc8J9tLUZmDFEvF9pM+gkItCi0XGlACDR6TQACDRt7RJu+07YcaDLincwBg32omGbhhb1UHBZdpgP1mqArCntDBTMThy9DC3YSAw6De/wil6vtOvSVNxMtaiw50PZsaw0KbQdua0FIbDbKdowpDONQoAXlryTS4sjErUYVNgdsGsEVkdDi3okrCI9xAu3mUjSwPqhNpUCL1soAoMBGx0WTscKpzBOJNWnHNVmMMgAEEiasvhSnRXtgR1Vajkd72YaVIaW9FqF/ZNAAFpUekhF6zlfeCXCXgu7ClbXoQtfmiWRrMmgYReFgoBaNAZFC147WK+BzQd1wlpHQ4tGk95tAFFTi07VJJDIeClDHYxBJxIJgKTBgG0NN00qXVp3shadJusL2Cn8jqStLb26iSQKg0bBS6RhfQPGIpCk7ailWTPc64W3ETLWM+lUTSKRhNUUv6KxAgiy9qJBKfBuTKVq0Rna+H1IelHgNgNgvMqjtzmZjkfF4j/5f88evfiC58rKSjs7u4qKitEGdacKvQ8fPuzt7bWzsxvtBzoUSbxkyZLAwMCffvpp5KtEitDF96cGvWSbcj7bgEreeSEn+7R0fGwU9BJ941g1V7yxTqAVVtlx1ctuucOmpjZ+RWZ8ck61gFe/c7UmALTMZtFGJ2MYTc9M1Cuw01fsNvtbOA1lNZXxCcmijo4DbnDURs8tiC9sy0iMZ7bwUwN8AACOBy61tTYkJaS2CjqvboMj4Y77ooQCbnJCPLO+vqNHacDZ3PtUXkMvMzsz/twxQNKPLGELGssS41KbeaKCizukTwoAAKJ2Jnfg2GoLAMD6S9W9gjI9MgDrDrKrEwBDn9PJr06/uGqFqZbBiq4+gY0e2BuSyBWJ4uPiQ3aaAH3n4tb28oz49Ao2p+iS0lXrvL2TU+J4lVUSLnUvdqWy07atrOFj6KXoFDa2l+Vk5JYw22uzMfDvbuZxcuPPrlhhRibi6KUfTKrhF4VqU8gmDn5tfGF2QkJhVYNQ2I0NOBMORV7jsxuS4pKY3K6mnGBtQL5c1X4Bc8DOxFfzKyIxfXfzaqI1gXU5V5BR25KaGF/PEeaE7FGU3sw6gp3hh13OUvSu3nVR0FLqqEsjUWjX6tsq8jKzC6q4tTlaGho5TfzDPoZ48npBi4chObSsLSOysjgrJau4VthUBHUE4GphPYdVkZCYxu/sSjvuBAAwsnYQCHlpiQmsVn5m8DYAgFdkVWt9Q9B2NxMDbWB1oJnPv5aemFtS19YxbMBZK6u2vTw7KTW/JnO3DoZebnlObXJcfC1HUBF/EABA1vGrb+ssy03PyC3vam901YF31agaXmVOoeNKK7edJ0urW9mVmXGxF/W0wIbDMbz2tuS4+PzqJndbEFnFPiaVw7GuuQIA7TOxce0dXYUp8QF7vfUOJgmaqxLjUllVOdJYCn8ctxwrrWazKzLjYi4sp4AcVntZZlJGOYdXE20AgKnr1g4Bk9NQm5KQ1MgVZgX7AwDk6F17JkPAqU2OS21pF5zbrARU6yOJAj4vNzm+oILNay4wpBPdt5wtauhgF8fHB25VKB/EFTewmWXxianNzARtAEIyqtubauPjEzmCjtzQjQAAQ7Or/JprFdeyk3NKe3j15kSi07YTZUxOa3lmbNQ5HQq4kMtqrCxMSs4TtjetNSMBsLa2u6OspTktIa6O05EduoVI3Bh1rZFfVx4ffdGKrBVT0VyRn52WU8xMOKRoiXTfaUtbGzc5LqG+XZQbvgEAcCCPd1lfFztrXsxpp2iQtx47V8PuqMqIj72wnwIosUXNXFZZQkIyv0MUc0DJF7fwPcDnMttbWMnxyS3twqSTvgCQLxdzGuuKd7nbwF6z7yqP25ASl9zI60jcr62/9wq3KAwri3AgoSrj8EYjB59OTg4DACPPA+w2dnpcQg23Ky/cDdBd6gXN+MNUbI2gMvYEAMA6ILssRHFEd9W1xvbi9PjMGiGn4CIdgFXOwX31JdVFmUnZ5Z2CevyWtyMog8+pj09Ibm3ldveKlAecveqF7RV1tYkpRUJha2pcdllafHGzqDYZmxmj6CdXsXmsovjETDa/MzfMiwjAvtC89obykxvtTPRIxt6HOdDmRGZbd24YNmajuYLV321lpNRbVLTC4wQ9F+jFl1zduHFjDOdyqtCLk57H41lYWIzt+y5atOjEiRPffPPNSMqqDJkS9K70PNZWEadBACTTvS0NmbjjNgp6AaA7tHBKbchAy8BS1M+1Xq4RkNWUfGot3gG8TsexMkLGRW+7iGWvTwKAsDGqvOqyP6BYlrYL3M3h1cFYu7W9tYBIABWctq3W0BZNI09BU5ou2bG6rWW9CeZk69rWCJXQCwDYkiGMXw3HDW1cT3c25TKg3wZoRm7sDjaDOvTMbhpQxYz0AsAsp7alXNi1woi65UxKVtguDL29Pvbwdg9k6FVwDcG+C4W5EbuxapKTajiHFcfQIHqLALBs4bKcDAHVbG17J9tcW0OKXpKm8xpTSDtN2xqhwBmOGexuEzFl4wuHWplxO0JTW4sva2M+cUhha9JeK4yO5HPXuJmBLgSiW1t7rb0e9GOIZJ0SjsjfxdT7SBYzcTcBgCJmcVktywmA1RF1WXtXA2BdLugIsoMV0fc7w2clKF6bK8PKCg7iFzNEr7nHUW5zqdsKOJdvdbK4Ln4DfKQg0i7V8E8waH6h2aWRkHaULen1iduJAISWdZSFr8YeZUiHEuqKQu10dyS3loTo4s6xjl1ze4OzPqAxtC0xIfU2n+Ez43H0NqXsg5YQGKnNnQFb4GgqQUM7nTMMvTvbBEwHPTIgEDSlXm9H0gE4j0Ay3sttvQaA9pX67gh/fDCW4LAjpy0HzgVH1XTE75auSNhxoigDnyDXcKtjMx3NpR4PACPRCy0qZLdtwgaczxR3FZ/0IEHnDHcKFZWD+7tOFacHSAecbSzhkyWJpt/a0eVmDdHbI2w0pUBtdFZvaW+vJsjQq2Fsz+sWrMaaz8brMJ8ZL7+bknTNuT29m2wxXJFpYVWdUf7weWZjVnPOGaXSV50trks5riMbhNDeeJFdFQWvIXjNrKzmNPsaQ/T2cfP04VAOJaiMl+4PT+89W5p8GkJOx/9K07VQTAvS4cym2I3OAKyt6+vwt4ZhNv6neLWpMLeDsax42FIkqnarqMvPXg/6Z7IRDiWbDExXGdNhTPMAQVOGSvQCAE6XNgdhF4v98fTmnGC8McjGri3cqtUK2Vn4HujiVuLcXu64t41dhKM34zCkHpGmXyfs2mALbwj6K336OwoNgWkpu3WrCRx0qeC2b7ClydEbU84J8sOWrZDNGtuq1gLiiUJujAsAOlsri6sbGnIAQSOqsm2/u+L81HJbS3yli26jsN3HCKK3t71EDzYo8WgeO/uEJgB29ZwGN2MM4hSbpo7h6G3u5q7D7p5nE2tZKSGwcuQ1HB6spqX7ub6mZG1sRoq+wrOzh2e6XHNfaF5NvLSZ4yu5ZzdivgrZrKmtEuvfmtEN/assDBREetLd5wW9KmGmGDiF6MXp29raSqfTR6Pvn/70p927d3/++ecT8XdxO6cEvcdSGutzgrZhG5PfGb4e3jVHRS8AkddaAreZWfrGtGftIAKQUs89hPUZ2C98jwrrEsdFb0stvB3D7Xhqa+4OYOoq6u+tr6urY8F/zNIcEpHQKuxsxA6xwEyb1XvbGtKlqQAYNuCsiF5nn/TWFLmrZ3qN17GNoTh+uL69Jcdq/f7azHDfZHb0etPwwobjLmTc63XEK6IKvcE5zfxWqYV1rLpjfgrXrRS94GxG7eUDHh6HMhoSN5MAwNFL0mTsDoour2LV1daJukRbMfQ212O3OVifQxwBTyRs8sQfeQDIa2JDjwnb8GVWRGK4sPKCLEwjspQb4e9s4LRJ2JpPNTtTEbN19+Xy2H3WmW39LtZ6EL3sZmnk1XuF7BJZQvjXOrY2Z6cMve3djb0DlzauxCPsyRHymxrwJqhj1V7ZSAMmG5uaio1I2qmcgV228MYUWsYNlvn7HluyGjOO+ESz8g97yIvIbenY7QJ0LNdHp5Uy6xprGzjC+iQcvTk7PGE0ulFLV986K2kuI5dZ7QmMrWvlZl0JsKJC/sUy2YelD07ODbyGdcC8ur93pSl+iwY6+vu727INIXrZR2WGDaHXLZxTEii3bVz0alhsSitmsZnXDm9co5hKvj+EXrrFifD46loWq5rV2zfgaQfRK6hLly2zWlffySYQpF6vvt36gf6uBllnripOockeBRmmNr39zRYyFGterK6LsVWJ3oAi4WXXIVS5huSUhw3NyF5h8s9sxLzeHGnPt0uorz6vhF73c0UdbRxZ+9alnHSFXq+oRToJ4rqzk10IaypDLyCQNx29UNPUWp5yed1KhlwE+Y7BCqdzyTk1zIba6pY+dt646D0YX5G+11ee/Forb/cq+RGw8D3AKYmVHXs0ihpw9O7bANtCa7mxsKerSXaLqGOVrtAG+y6XZIf6aFgHsIvOUACQo7eY3dk6FLPCawWw8b7SUXjEOTjnym6/uJomDwa9ntfgIO1EsEySntWJC8nMmlpmVV13X4ffSojeDlnn2XCpmnnVG4CTbcxomYVgxFyvVz23HD976MK1gnPS1YGNoiZPAFafLWm+Ir9jWNT091iZLt8XmpcQJPW8SzlKNnuYw5zOVfevskToVRwUnuz3eu/fv89isWg02sif2pgzZ463t/cnn3wyce5OyQpngpZ3A7818NTp09i/qLRrLfmXxkav5Z4IZlJofG37dg14czxXwo3cK+0fDgcuNOaGA0BLbxLt8rCDT+Qm9t19wuEDzsPQq7umsVOwYrnsxoX133oh19dIwfkw8ee0M/HpTQJlRSVfhdeb6AQpYu8RIapNwOeQyTSH+q42beVJnexGXkF21uX9K7RoR5pyDpXX5MJrEBtwdjTCylZEL6cVvzGeSGSmBMNhPRWbDL1g1WE2M7+C3YIPAuDoNVgT3cm8TIdOnk2FQIbeumRZPnDA2SckT1SXaqAJnZrEen6oHVYmQeNsfivm9e4UtJVYYGcJRFp2k3CLmwUAFiU8/tGctqMuNjYb9zdUZ3T3skwhfsZCr9XB/KJTmEOKzfWSVp3kdzb6WkHsu8c1VJ63k7lVUuuOZtSmBKzv7y43wsAWWibM2In7LaQ9qfV5QbbGJwsas/Zr4DNSGtp17U2ehiC0TJjkCx93dPzOyNGbtQUjNEW/QtTrtw7eWggkWmLLMK+XiM0VauyMahDl7cfnemUrnHH0GmTx+k6sxYe6CWZO8YLiU5jX2ypf8b7jRFFWsBusgPXR9tYCxtDiNxBRyb/sA7lH1tvd3l6BV7KQ3e6HLVUlEmHttaw2skXcIUTI2gn3ejOCYM6e5wqZMXA8gEgzaOnow9Hb1VZJx4SgrN0maquSe730lU493e0r5B6rQoYaBpYd/T3rVmA9n0A+mC9K2a7a692Z1lIa4o17uXBcZm9ca1EwnPKFlaGXtLZuNRsVvanYMqeVp9IaM4/Ic8BSqkZvfRI2PgEAnr3niVhBQxq+LELBdnA6qyn5tCP0iQ3PijD07snh5x2ET69E2rqmbjjgjHm9LSHuMJ1XeAEr/hB+SRO0TOrbahVHnC18Dwgb8/Hup+WyX9hSiKN3ly/0ADV0DNu7utZbyJ5ZMDsYrnvbWVkBpd0nreBzoRy9WQ2CY+6yxxksJtXcrr+/tZzVuNEWuBzLKQvfzs0/qViXHeeyKqKwHkSgNwqFo6B3Wxu3xBRrYoKmTqOwY/iA8+jotdmY0Ft9kYJVj2zsKOwVmulT9oXmxQZKF2LmNgmOuCnZDMDyzPY+2xVKc3WKNk9i/wX1enE/9f79+/n5+e+9954ifefOnWtvb//RRx+NXGWt6IWP3H9yr3djQFRDWqi8FUnWm0SiZtqYXi8gmZZwelrrUvG1JGbeB7u7hBmXgsKuZPM7WndZU+BI8tXKbk7NuZCLpY3CgYERc73D0AuIDmdLuniNkeEhFy/HZ8eeJABwMKZCxK65EBgUEpmaf24FAKQTOa2CpvKw4KCy2irOCPQaRDA769KjLwYRKabXeAPNpWkhgecrmgXlV7fK1v5Ia3kgpqy/s96VBIiatEausDoW8x5Uo1crpamvLCr48hkzhuN+QY8oPyo8KDD8WnGyjVwyAIAcvYAQlM+uzz6Hn8TRq78isKeHExkekllcw+WrRi+BRN4SV9dRn2ZMBh6743qE7AvBwelF9W1tfHyuNyK/ua2uJCwwNIfJ4V0LpGJ3UMf4+r5+0VojAljuxunvFmXvwO6VY6HX0MKvh3kBu9NL53oN/C+LRHUbTQBluQ2vo7Mw6WpQyIWcggIatoDOzu9If5ew6LB02CC0TNjeKrh6Piwhq7yDXQ5nyola+Y38usKM4NALddzO9GMuRAD2ZLH5lRkhgRcrGvjD0QsItiEl3YLmqHNBiQU1NU3D0Lu/pCQ9KDAku1pYGggfpBReLsLRCxgrjgo7RalRFy9FpYtEAntj+CgQVTOEXr9DyfyWsqCoRGNt0onEKn5TeVBgcEJuuas18D2T38WrDwsOqmQ1Cluk6M2qFxSlXQ0+vi+osC32wrnQK2nCtmpdoBGUxdrjotTO/kdS+c1lQVcT1oeldHOY5wPDCliC3r5+HL19fSJOWXpI4IW6tu7cc3DuUzrXS9A8ls8TNVZcCAm6FJuVHbJ+qO8QiK4RlZ3cpqvhQbGZ1T0dFSbYusCRA84ETcPato6KzITgsIvlRVe1iZTE6rbmsrygoNCqJkFBGBxlgXO9I7zercfTeY0lwVfiDHT1ippFtfmpQUEhqQWV7vYGqr1ez/PdAtbF82G+VAazouRCSFBSHqs1L4QMQFF1vuJowKHoKi6rIDg4tJnZ1I2h19Arpqe7Pep8SE5ZXVubFL3H0hqbSxOvxF+ga+gVNolYBWnBIeH1bZ1xez1xtONqWPge6O0VsUuTgwMvNLR3pwR4KqIXEEg7E1idrczLoUHnrqTWRGMPwQRaMqtb1NNiii1GkqN3/fGYHn5LdHhQ0Lm48iRscp+wPI8vHmhM1ALA3MF3oFMUIx3gkjaF59n4jlZmWHB4WSOvu2c09BKulnNaq/Owrt7c0Tns5aKxvF4i3aymu7/xWmJQ6KWaFlHpeRciAc71ytHrfjK+myezOfEINEvfpqOv3VxXUaShjjO5vRcavRKJ5Oeff05LS1u2bBnuSM+ZM2fVqlV/+ctfVP5U5EjcKoY8OXotV61abYn7enhrajl6eK8kg5Vr15sb6QCg6eDhTZWtI5W399GcprRTQy+1GVmt9fX19fXxsjXDPSo4sOjk5uXr621vbeLl48mQDQZiOZi6uUKHGG4r7N0c4GMygaSx1sUDy8PD2gTLhERf4+IJs/XytNCH6clU7fUePr6+vmss9RzcPc2kWUj/EAg67l4+3uuhw0mkGLl5wphuTnbKj/kwMsV8tTc+dkcgOrh5rTLC5gjJmu5entq4461J9fbxpGNP2HQTO19f33XWcE5L33INVk0f59WWSt6hrpG3O1xeBJe6mK+2M4eRAQAunu5wNIBIdlgPK+Joa+Pk6WUE3ToTN1d8thK+v+TmAsfdiGSqp7ePraEOIFDsnN19fX3dHW2s7devtcLGxUg6jlgmXm7OVA1pnSjLV/t4OmDSajq4+0AGw43m7I75fNCVN/WUGYadAkQtg6oOwRozOgC0de6YMwKAnbPH+rWQc3oW9l4+vr4+Pq6OttLnFVPvdlGzmXTZKli5zn0l1czT28fX29PSUDoIqaVr4o4lc3Naha/gptCMsQBPExs7z/VwmFTP1mWtoXQuFgCw2snN19d3vYPtShff1dq4G40bqOfi6e3r6+vp6oAvRLdzdTPFzwDd9Z7YXAggmNo6+Pj4+nh72ZlL81zl4i7vD0SaHux6Pi4UEiBq6Tq5QfG93J0ZmoBAYbhiHcPWxNzVTep0Lbew8/b1XWdramy7HnYaby8bY11A0anhs51MldwsIl0f69QuFBJtLWwObydbczdPHz0G0NI18lzvaIvVy93JFm8hXau1Tubw4iIQtda5wXp5e7iZ6Q7vkrga3p7rTWTDugZr3aSOvbTu8I+OiTVU3sfH1c6MCACFYYB3cnfn1fhiBoqWredafMISMFavd7GG/QG32cfLmUICdIMVHtAKXw9XRxocDNB29XKDa4ABALrGXu7QhQWAtMbV09fLTYdIcpJ2uXXQZIOTtZnyeRwYj6Jt5O4Ne4ul9kpPdwcYRCQ7uEK1HWxWOrl74DnT9c28fHx9XGxIAND0zLCu4rvewVrqsmNFAoAPOCfYYjcBN0cb7Poi2Di5G+vLRAEa+A3Bx8vDSl86HqZv5+rtshK/GCna+l7ua7ETJGsH2MF8fXxWmUvvSOaO3utXY5cSVcfHx5shWx0tLUBQSaAAABHmSURBVJ/IcHTz8vXxcbTSdfX0NKABuo6Vl5N0iFjfxsXFFs55ExlGbp7evj7ea1bouHh4Gir2XKC33l3ao8ysnRytpd12vZcbTIkNALpjfc/VAc4pAABMrRzsLKXLGAGQ2eztvcoMjkKt2hzBTtuu1P/wZE/w/4uOXolE8uOPP0ZERLz66qtz5swxNDTkcrmKP2CpCNex958cvZNpx+XOzOYKJXdgMrmgNM9GASOvkIrkE9KFUeOZ4LLrfF0OtmBkvJgz7LyWrmlb1WX5XX+G1W4S1VkRWhriLX9enEQG4ySBc71FUeNEemFOU43si5nlU36PnWL07tix40+jbPiLOo81e6qIurCwsMWLF6vMe9GiRZ6enrdu3VKM/1j7+M9Mrly5ksVi3b9//7HSyiM/ffSejs2vbeTGHYHv/6BtZisQlZjfyq71l/pRM7uuqHbPWAGE3qfQAFOJ3t9//10oFOaOshUUFPT19clB9bg7YrG4oKBAZd75+flcLvf3339/3DwV49++ffuzzz6b9JPBlCyzetz2JpJIZLLyL2Q8bhYo/jRRALb0sB8PmSaWIzOnnQIEApFMGj4UP+1q8ZwbPJXolUgkv//++73Rt8kN5OKAfPDgwegZ33tC7kokksHBwcddV6VI7meC3ue8byHzkAJIAaQAUkClAlOM3mE0eqEOn/6As8oWRYFIAaQAUgAp8JwrgNA7ZY8HCL3PeV9H5iEFkAJIgedEAYRehN7npCsiM5ACSAGkwIuiAEIvQu+L0tdRPZECSAGkwHOiAEIvQu9z0hWRGUgBpABS4EVR4LHRKxAInnAl8JSx7jnL6PPPP9fS0lL8eekXpROheiIFkAJIAaTA4ygwPnpffvllRZyUlJTcu3fvOaPeszdncHBQJBIRCAS5VrNmzXqchkBxkQJIAaQAUuBFUWB89C5YsGDWrFlyoqxevfovf/nLnTt37qNNpsDdu3e//PJLPz+/+fPny4V6+eWXJ9eJlhHJgKD0s8STy2fiqZZqyj6SpyrNUg0qNOkpbu/RFX/I+ikWjIpCCiAFkAJPRYHx0fv6668rftT2pZdeMjc3DwkJiYqKikYbpsDFixednZ3//Oc/y7mrpqa2aNGiSbTgO7orZx8RqAVcf5r/1E+JX1uFf3l+uMnv0Y3nHmQ/TWPUAq6rn/7rIiflr5MPtwsdIwWQAkiBaazA+Oh9//33582bpwgVtD+uAnPnzn377bcn0S9es931lDmHFzfreLdKa98ycXk29pwSq7QHfnmGQKBSqYwxNzqdjn/wdbRMUDhSACmAFHiGCoyPXgDAG2+8MXfu3HF5gyLgCsyePXvJkiXLli2bRLu+tmrv1KLOr/yriWQ4GnrfNlgzkeQTjLPo3Ed7mF9PMPJo6hkZGRkaGuqPuRkYGJiamk4j+mobmJiZmZkYoM/zjNbsKBwpMKMUmBB6ly1b9sYbb8yZMwfBdVwFZs2atXDhwqVLl06umyD0ysGsUkACgWBkZDQmdqUnDQwMGIxpQDIt+Dv1GskNvd2i7r6m1GlgscqGQYFIAaTA4ygwIfQCAJYtW/bWW28tWLDgpZdemjVrlrq6+rgQeqEiqKurz5kzZ/78+a+//vqkuQsAUIXeL6s++tkIm/19OfRG5Y2bJlcfYyZ4ar3eOSEfFl+/5Zz1qRyQw3aSPvj1RMl1tcAP4z+4FV7wbXLPfxUjPLnXSyAQxnN5rQLj0/3NIIC1tcdaPvY4l8k4cQOuxsJv0D/uRqAevFra3S3MjoyrarpGIJIquM1xFxM4PNG1S/uGfb38cfNG8ZECSIHnWYGJohevw9KlS99+++0lS5YsXLjwVbQpKLB48eI333zz/ffff8LGHobetdXfBrNv3R18WMD+bm/5V+fav7/zaPBa13dHqz9/9+r39wclZeLvI/7PLcngIE/wQwTv5s+PJDlNSmCeWvTOz/rp7qCk9m8/BrO/O8v57l93Bz//8JePbw929H+Fmfrdf+5L/vLJd0Gc7/5991HPB7999+BRfvEQp58Ceg9GZHIrU00w11cleh2iqi/sdxrWTEbO20/ItnUrgf6BvPxDhngcqvbyswGB+HYuMkbc1RAuPQo8vsMZrNlw4sSJuNQGVi5M7+kPD0+cCEoNDDzmbIbnMNr/eub+vb1tzk4uESklZfGnASAGJhQnXzplv865p797t7nuaAlROFIAKTDdFXg89E732j7/9g9Dr1rojbSvH0kkv59M+VQt7KPc/z4clAx+IPh2ScB1HL1rU66r5f5H8ujR2ZAP1QK+/PcD1eidG/7x4bYfVsd8pK64djroxr72/3lm/EMt4PqE5npDbjT+Ivm/nZ+mfP/wr/3fqYV//Pc7g7yyz5k/POr4y9fmmZ/ZZH32yV1JS99nNtmf3bg72NX5XehX92Mz/vVykPRpQI7eOaEf+bf+zz3x41mK9gR+6FP//d6Cf+KOssrGGtvrdT4cw2st9TSVjjkro3dDY1db4bCttSPQwXpYQWarHDZcqKyM2Ojk5OS0dhU8a2ID952cvLftGxCUemH7Dqut8IThsZFGukDbxr0pefe28NSww57DMhz1kEC/UMEP2bQGAEAkU8xMTTXhx5cJ/idy26ui6U/1fa5RbUQnkAJIgT9CAYTeP0LVyec5DL3m3Xd/+OdPPz969O8fHwxKJN98+u1PDx62/fO2uO9bHL0PHw3CExLJo0eDDx5JBiWq0ftGylc3bktu/3rXKOxD6Qhw0I3NvbcfDEpaOr+ZKHoDri/86z2D+E/Svn/414Hv5pxXQG8/XMzlKbwpefC7VwAccOb+/Ki38T/qgR8qwlWO3oUxn/XfkkgePXCP+Vg+Iu3CvXl/UCL+v99PDr0Glgd4PcKDbrjHO3LAeUMVK2Z4w4SWjUQvAHKvd01tSzVMElyU6r4WAKBrtXagLRMbxfasakyDyCQS1x6IiA44kdvUoEsnbT+XNkH0GqzxbOL1DvT3c/KPAKAZVizo7+/nFwVqEkBAIbe/v5/XWOuySm+4wegYKYAUmBEKIPQ+X82ojN4bOsn/Ugv42Cj100UB12mJn84K+tAo9V+LQj/ST/7nY3m9agHXSelfXb8ruXnzjs3Vj9QCbmwX3Pp9UFIv+vrP0F2emNcbcGN56r/MUv9V9dOjT278ZJr1+T/uybze/m9iP7r9+a8PHz142PPFnZ4vbot/eXDjrz81//qoT/CFHK5y9KoFXH8z7t/9v0l+++2eb/InagEfOjT9fPOhRPSX716TPRyobBi517tu0xapb4v9Mbde1yLsPrTZUTFwuNfbzSsdtnE7MfTaJyuEJ57dKxtwHkKvoK62tLS0oqZW3CusgJHr2yF6iebWq+zt7Y8GFqUdtbe3tz8WncdtqZdmlhwARt/MPXZyymJN9LSJBACctnMqkzU1qFmsdv+1ABCI2nrmSTV8f2eT0TNAZ5ACSIFprABC7/PVeMrovb4o4pOTTf8d+c8xQ4re6r/9L+bvv0oGB0Wd/4sR3fplzLlecsZXn9we/Pa7W1c6f/nt4SC/+xucuxNG7/UFf70n+elmyvcPv/v29hXRD58NofcrteKf7965d1zwXWA1ZO3lG/du/z74683byxWGlBXRqxZwfUnsZ53/e/jTT7cvcH68+UjS/7fv3j4nc8oDrqtsGBl6bSKLmpIOrTfASGu40jGDxbmy1wM/lNN3GHrH9no3ZHK8zaVeplty01mj5QCsqWTmQTMUvN7+ylDMMKnXa+l7MCwsLC2nsSYtLCwsLDABDjhbrY6vOk9Sab880HjdJg6bU1mYGXbIAzAsM1mc6CsxbbWZFjrA5eCFoooaAb/da410vlmeCu0gBZACM0MBhN7nqx2V0fuP6P9zk3kd/3f7l0eSb76RHf7tx2XZtx5KBlcnTmiuV+53vpvxn7/ffCR59Ki9T2nt8YTmegOG0Dt8rrf/qz2iX5jXb/7910e/3rrP/PvP8Z/ckUgGy9n/WZkwtOxrGHrVAq6/kfhFx/8eSgYH//7hD4tCh7irNg569a0dN3GE/E0OpvpmqyKLmkujj4185WgYemvZBT7DtrQGfMBZy9S+vSmW4X24Mj1YG9CSG0VGenQAXGrqMPRuSRNxS1JTU/Ov1fVyy1PhVsrBBpwBAM7Oa7y3Z8TvXmNMJu25mH1qs8lE0Au7HVFzV3JDY0qAFgAkTYbvDl+aBvwB0W3n85kJ/hqE56tnImuQAkiBKVQAoXcKxZyCrJTRC6E179xHvT/dsQj57IP7g3XNH3/035tLwj9UC/hQ78Z9yaN7egFK6P3sgSS7cQh1agHXR65wfiPx8yOVQ4PAOJUfA70/38r94eH//esPb1z954d3BzuZX/X/JuF1frX4wkdvXPwo/NPf//2PH9+5/N0tOPH8IK/gywe/PwARw5dZyR8F1AKuL4r+1wmWit/9UKmmzOuFnq2Vf3xXY8rV5Oqmggi5p6u4Mwy9o3u9JO/Uip3L9fNqWkSd3eER3t3tlToUAIB/Vc0l3IyrhY2Be5y80lhxG5Tsop7JLL240Xt7Ruo+M3bOwaTKxm3WYILoNVixtW+gZ42FtrX33qvH/AAgbA/LjDzkraVv19jV5WGko1QSOkAKIAVmkAIIvc9XYw5Dr2bid9//LtnY/5t/4VefDw421H+s2fPb/XsPzjM/M8z68R/Xsfd2sBXOmX+788kPDx7euftG+DjoVcSefH9C6L386V/vYWu6JJIczj8oSf/+6O5gb+PXlJh/vBbw4bLof1Bi/nH1379/8a+faXE3P/3Xl2lfPvj485u//nhrSeBY6JXbMGxHZcMoolffwCSimNNZn2FrPtLjhQieMHrJhqbm5uZmDDJJi6G7N7c2eTu2lMrrdHNhOG7GhlNxvQNicX9vfX2dtbm+zDaCrqGJlibwv1B6xZtosC+5IWeHBpgoekkUg7jajlZ2W11lbXtrISCSStjtDbUtQn57R0O6MfWpfkJDViP0FymAFHgaCiD0Pg2VJ16GMno/cq34jyWcK/10U/V/dlR8KYVT9Kf+xf8eBqrRDkd6vSpjTgi9CrO2MJPgD93L/+MY9Ylihtq5X3rl/EsaEvXpjur/rIodehQYOeCsmHbYvkrRlNCrr69vZG5uaqzo6SruD0Mvi1O8fdiW0zRshbOt+/G85EBA0vD237p9+/Y11kZUuuP27ds3OBvI7CFs2LwNz2bblg0UMnDfuG371k2GABg5bsCGqQFdx8nbfmLjxWRTb7e1VKLpNW5HVHR0ByffmMhw9dlgBn1utCEFkAIzVgGE3ueraZXROwStYVia+OEfiN5hJJ7A4ZSgd4I/JGloaEin05+v1h3dGuftx06fOn1sm+PoUdAZpABSYOYogND7fLXllKN3gpCejNc7AdZOsHSV0UZrGD09PfwLCoZjbsbGxgTCxFzP0UpC4UgBpABS4I9RAKH3j9F1srm+brNDJYf+6MDR0PummfsfXbTK/Ged6B1DQuIEtjGSo1NIAaQAUuDZKoDQ+2z1H176e3Tjl3bXqKTRHxc4+1jn20aqhzqXajLmbS3444pWmfOsk32vr9wyXBp0jBRACiAFZooCCL0zpSVRPZACSAGkAFJgmiiA0DtNGgqZiRRACiAFkAIzRQGE3pnSkqgeSAGkAFIAKTBNFEDonSYNhcxECiAFkAJIgZmiAELvTGlJVA+kAFIAKYAUmCYKIPROk4ZCZiIFkAJIAaTATFEAoXemtCSqB1IAKYAUQApMEwUQeqdJQyEzkQJIAaQAUmCmKIDQO1NaEtUDKYAUQAogBaaJAgi906ShkJlIAaQAUgApMFMUQOidKS2J6oEUQAogBZAC00QBhN5p0lDITKQAUgApgBSYKQog9M6UlkT1QAogBZACSIFpogBC7zRpKGQmUgApgBRACswUBRB6Z0pLonogBZACSAGkwDRRAKF3mjQUMhMpgBRACiAFZooCCL0zpSVRPZACSAGkAFJgmiiA0DtNGgqZiRRACiAFkAIzRQGE3pnSkqgeSAGkAFIAKTBNFEDonSYNhcxECiAFkAJIgZmiAELvTGlJVA+kAFIAKYAUmCYKIPROk4ZCZiIFkAJIAaTATFEAoXemtCSqB1IAKYAUQApMEwX+H44HgNMbFpjsAAAAAElFTkSuQmCC"
    }
   },
   "cell_type": "markdown",
   "id": "2b1de02b",
   "metadata": {},
   "source": [
    "今天的公式很多，如果有的同学你的vscode的ipynb文件中markdown的单元格无法渲染latex格式的公式，你需要去插件市场安装插件 markdown all in one 然后重启你的vscode\n",
    "![image.png](attachment:image.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "283967eb",
   "metadata": {},
   "source": [
    "今天的打卡内容介绍下特征降维中非特征筛选的方法\n",
    "\n",
    "首先需要介绍一个经典的工具SVD奇异值分解，他是很多降维算法的基础"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e3bda85",
   "metadata": {},
   "source": [
    "相信大家在考研期间都考过线性代数，今天我们来回顾一下经典的考研题目，你就会知道之前的线性代数就是在为这里埋下伏笔。\n",
    "\n",
    "当然可以！在考研数学中，特征值分解（Eigenvalue Decomposition）相关的内容通常出现在线性代数部分，常见题目类型包括求矩阵的特征值和特征向量、判断矩阵是否可对角化、以及利用特征值分解进行矩阵的对角化。这些题目往往以计算题或证明题的形式出现。\n",
    "\n",
    "---\n",
    "\n",
    "## 考研数学线性代数典型题目：特征值分解相关\n",
    "\n",
    "### 题目 1：求矩阵的特征值和特征向量\n",
    "**题目**：给定矩阵\n",
    "$$ A = \\begin{bmatrix} 4 & 1 \\\\ 2 & 3 \\end{bmatrix} $$\n",
    "求矩阵 $A$ 的特征值和对应的特征向量。\n",
    "\n",
    "**解答**：\n",
    "1. **求特征值**  \n",
    "   特征值 $\\lambda$ 满足特征方程 $\\det(A - \\lambda I) = 0$。  \n",
    "   计算 $A - \\lambda I$：\n",
    "   $$ A - \\lambda I = \\begin{bmatrix} 4 - \\lambda & 1 \\\\ 2 & 3 - \\lambda \\end{bmatrix} $$\n",
    "   求行列式：\n",
    "   $$ \\det(A - \\lambda I) = (4 - \\lambda)(3 - \\lambda) - 1 \\cdot 2 = \\lambda^2 - 7\\lambda + 10 = 0 $$\n",
    "   解二次方程：\n",
    "   $$ \\lambda^2 - 7\\lambda + 10 = 0 \\implies \\lambda = \\frac{7 \\pm \\sqrt{49 - 40}}{2} = \\frac{7 \\pm 3}{2} $$\n",
    "   因此，特征值为：\n",
    "   $$ \\lambda_1 = 5, \\quad \\lambda_2 = 2 $$\n",
    "\n",
    "2. **求特征向量**  \n",
    "   - 对于 $\\lambda_1 = 5$：  \n",
    "     代入 $A - \\lambda_1 I$，解方程 $(A - 5I)\\mathbf{x} = 0$：\n",
    "     $$ A - 5I = \\begin{bmatrix} -1 & 1 \\\\ 2 & -2 \\end{bmatrix} $$\n",
    "     解线性方程组：\n",
    "     $$ -x_1 + x_2 = 0 \\implies x_2 = x_1 $$\n",
    "     取 $x_1 = 1$，则特征向量为：\n",
    "     $$ \\mathbf{x}_1 = \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} $$\n",
    "   - 对于 $\\lambda_2 = 2$：  \n",
    "     代入 $A - \\lambda_2 I$，解方程 $(A - 2I)\\mathbf{x} = 0$：\n",
    "     $$ A - 2I = \\begin{bmatrix} 2 & 1 \\\\ 2 & 1 \\end{bmatrix} $$\n",
    "     解线性方程组：\n",
    "     $$ 2x_1 + x_2 = 0 \\implies x_2 = -2x_1 $$\n",
    "     取 $x_1 = 1$，则特征向量为：\n",
    "     $$ \\mathbf{x}_2 = \\begin{bmatrix} 1 \\\\ -2 \\end{bmatrix} $$\n",
    "\n",
    "**答案**：  \n",
    "特征值：$\\lambda_1 = 5$，$\\lambda_2 = 2$  \n",
    "特征向量：对应 $\\lambda_1 = 5$ 的特征向量为 $\\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix}$，对应 $\\lambda_2 = 2$ 的特征向量为 $\\begin{bmatrix} 1 \\\\ -2 \\end{bmatrix}$。\n",
    "\n",
    "---\n",
    "\n",
    "### 题目 2：矩阵对角化\n",
    "**题目**：给定矩阵\n",
    "$$ A = \\begin{bmatrix} 5 & -2 \\\\ -2 & 5 \\end{bmatrix} $$\n",
    "判断矩阵 $A$ 是否可对角化，若可对角化，求对角矩阵 $\\Lambda$ 和可逆矩阵 $Q$，使得 $A = Q \\Lambda Q^{-1}$。\n",
    "\n",
    "**解答**：\n",
    "1. **求特征值**  \n",
    "   计算特征方程 $\\det(A - \\lambda I) = 0$：\n",
    "   $$ A - \\lambda I = \\begin{bmatrix} 5 - \\lambda & -2 \\\\ -2 & 5 - \\lambda \\end{bmatrix} $$\n",
    "   行列式：\n",
    "   $$ \\det(A - \\lambda I) = (5 - \\lambda)^2 - 4 = \\lambda^2 - 10\\lambda + 21 = 0 $$\n",
    "   解方程：\n",
    "   $$ \\lambda^2 - 10\\lambda + 21 = 0 \\implies \\lambda = \\frac{10 \\pm \\sqrt{100 - 84}}{2} = \\frac{10 \\pm 4}{2} $$\n",
    "   特征值：\n",
    "   $$ \\lambda_1 = 7, \\quad \\lambda_2 = 3 $$\n",
    "\n",
    "2. **求特征向量**  \n",
    "   - 对于 $\\lambda_1 = 7$：\n",
    "     $$ A - 7I = \\begin{bmatrix} -2 & -2 \\\\ -2 & -2 \\end{bmatrix} $$\n",
    "     解 $(A - 7I)\\mathbf{x} = 0$：\n",
    "     $$ -2x_1 - 2x_2 = 0 \\implies x_1 + x_2 = 0 \\implies x_2 = -x_1 $$\n",
    "     取 $x_1 = 1$，特征向量：\n",
    "     $$ \\mathbf{x}_1 = \\begin{bmatrix} 1 \\\\ -1 \\end{bmatrix} $$\n",
    "   - 对于 $\\lambda_2 = 3$：\n",
    "     $$ A - 3I = \\begin{bmatrix} 2 & -2 \\\\ -2 & 2 \\end{bmatrix} $$\n",
    "     解 $(A - 3I)\\mathbf{x} = 0$：\n",
    "     $$ 2x_1 - 2x_2 = 0 \\implies x_1 = x_2 $$\n",
    "     取 $x_1 = 1$，特征向量：\n",
    "     $$ \\mathbf{x}_2 = \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} $$\n",
    "\n",
    "3. **判断是否可对角化**  \n",
    "   矩阵 $A$ 有两个不同的特征值，且每个特征值对应的特征向量线性无关（因为 $\\mathbf{x}_1$ 和 $\\mathbf{x}_2$ 不成比例），因此矩阵 $A$ 可对角化。\n",
    "\n",
    "4. **构造对角矩阵 $\\Lambda$ 和矩阵 $Q$**  \n",
    "   对角矩阵 $\\Lambda$ 由特征值构成：\n",
    "   $$ \\Lambda = \\begin{bmatrix} 7 & 0 \\\\ 0 & 3 \\end{bmatrix} $$\n",
    "   矩阵 $Q$ 由特征向量按列排列：\n",
    "   $$ Q = \\begin{bmatrix} 1 & 1 \\\\ -1 & 1 \\end{bmatrix} $$\n",
    "\n",
    "5. **验证 $A = Q \\Lambda Q^{-1}$**  \n",
    "   先求 $Q^{-1}$。$Q$ 的行列式：\n",
    "   $$ \\det(Q) = 1 \\cdot 1 - (-1) \\cdot 1 = 2 $$\n",
    "   因此：\n",
    "   $$ Q^{-1} = \\frac{1}{2} \\begin{bmatrix} 1 & -1 \\\\ 1 & 1 \\end{bmatrix} $$\n",
    "   计算 $Q \\Lambda Q^{-1}$（略去具体计算步骤，结果应为原矩阵 $A$）。\n",
    "\n",
    "**答案**：  \n",
    "矩阵 $A$ 可对角化，对角矩阵 $\\Lambda = \\begin{bmatrix} 7 & 0 \\\\ 0 & 3 \\end{bmatrix}$，可逆矩阵 $Q = \\begin{bmatrix} 1 & 1 \\\\ -1 & 1 \\end{bmatrix}$。\n",
    "\n",
    "---\n",
    "\n",
    "### 题目 3：利用特征值分解求矩阵幂\n",
    "**题目**：已知矩阵\n",
    "$$ A = \\begin{bmatrix} 3 & 1 \\\\ 1 & 3 \\end{bmatrix} $$\n",
    "利用特征值分解求 $A^{10}$。\n",
    "\n",
    "**解答**：\n",
    "1. **求特征值和特征向量**  \n",
    "   特征方程：\n",
    "   $$ \\det(A - \\lambda I) = \\det\\begin{bmatrix} 3 - \\lambda & 1 \\\\ 1 & 3 - \\lambda \\end{bmatrix} = (3 - \\lambda)^2 - 1 = \\lambda^2 - 6\\lambda + 8 = 0 $$\n",
    "   解得：\n",
    "   $$ \\lambda_1 = 4, \\quad \\lambda_2 = 2 $$\n",
    "   - 对于 $\\lambda_1 = 4$，特征向量：\n",
    "     $$ \\mathbf{x}_1 = \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} $$\n",
    "   - 对于 $\\lambda_2 = 2$，特征向量：\n",
    "     $$ \\mathbf{x}_2 = \\begin{bmatrix} 1 \\\\ -1 \\end{bmatrix} $$\n",
    "\n",
    "2. **构造 $Q$ 和 $\\Lambda$**  \n",
    "   $$ Q = \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}, \\quad \\Lambda = \\begin{bmatrix} 4 & 0 \\\\ 0 & 2 \\end{bmatrix} $$\n",
    "\n",
    "3. **求 $A^{10}$**  \n",
    "   因为 $A = Q \\Lambda Q^{-1}$，所以：\n",
    "   $$ A^{10} = (Q \\Lambda Q^{-1})^{10} = Q \\Lambda^{10} Q^{-1} $$\n",
    "   计算 $\\Lambda^{10}$：\n",
    "   $$ \\Lambda^{10} = \\begin{bmatrix} 4^{10} & 0 \\\\ 0 & 2^{10} \\end{bmatrix} = \\begin{bmatrix} 1048576 & 0 \\\\ 0 & 1024 \\end{bmatrix} $$\n",
    "   求 $Q^{-1}$：\n",
    "   $$ \\det(Q) = -2, \\quad Q^{-1} = \\frac{1}{-2} \\begin{bmatrix} -1 & -1 \\\\ -1 & 1 \\end{bmatrix} = \\begin{bmatrix} 0.5 & 0.5 \\\\ 0.5 & -0.5 \\end{bmatrix} $$\n",
    "   计算 $A^{10} = Q \\Lambda^{10} Q^{-1}$（具体计算略，结果如下）：\n",
    "   $$ A^{10} = \\begin{bmatrix} 524800 & 523776 \\\\ 523776 & 524800 \\end{bmatrix} $$\n",
    "\n",
    "**答案**：\n",
    "$$ A^{10} = \\begin{bmatrix} 524800 & 523776 \\\\ 523776 & 524800 \\end{bmatrix} $$\n",
    "\n",
    "---\n",
    "\n",
    "### 总结\n",
    "考研数学中与特征值分解相关的题目主要集中在以下几类：\n",
    "1. **计算特征值和特征向量**：通过特征方程求解。\n",
    "2. **矩阵对角化**：判断矩阵是否可对角化，并求对角化矩阵。\n",
    "3. **利用特征值分解求矩阵幂或函数**：通过分解简化高次幂计算。\n",
    "4. **证明题**：如证明某些矩阵性质与特征值的关系。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "591f6604",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "## 线性代数基本概念回顾\n",
    "\n",
    "上述题目应该勾起了你们的一些回忆，我们再来回顾下其中的一些基本概念。\n",
    "\n",
    "---\n",
    "\n",
    "### 1. 正交矩阵（Orthogonal Matrix）\n",
    "\n",
    "#### 定义\n",
    "正交矩阵是指一个方阵 $Q$，满足其转置矩阵与自身的乘积为单位矩阵，即：\n",
    "\n",
    "$$ Q^T Q = I $$\n",
    "\n",
    "其中：\n",
    "- $Q^T$ 是 $Q$ 的转置矩阵。\n",
    "- $I$ 是单位矩阵（对角线为 1，其余为 0）。\n",
    "\n",
    "这意味着正交矩阵的列向量（或行向量）是单位向量且两两正交。\n",
    "\n",
    "#### 性质\n",
    "- 正交矩阵的逆矩阵等于其转置矩阵：$Q^{-1} = Q^T$。\n",
    "- 正交矩阵的行列式值为 $+1$ 或 $-1$。\n",
    "- 正交矩阵表示旋转或反射变换，不会改变向量的长度（保持欧几里得范数）。\n",
    "\n",
    "#### 简单案例\n",
    "考虑一个 2×2 的正交矩阵（表示二维平面上的旋转）：\n",
    "\n",
    "$$ Q = \\begin{bmatrix} \\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta \\end{bmatrix} $$\n",
    "\n",
    "验证其正交性：\n",
    "\n",
    "$$ Q^T Q = \\begin{bmatrix} \\cos\\theta & \\sin\\theta \\\\ -\\sin\\theta & \\cos\\theta \\end{bmatrix} \\begin{bmatrix} \\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta \\end{bmatrix} = \\begin{bmatrix} \\cos^2\\theta + \\sin^2\\theta & -\\cos\\theta\\sin\\theta + \\sin\\theta\\cos\\theta \\\\ -\\sin\\theta\\cos\\theta + \\sin\\theta\\cos\\theta & \\sin^2\\theta + \\cos^2\\theta \\end{bmatrix} = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} = I $$\n",
    "\n",
    "这个矩阵表示一个角度为 $\\theta$ 的旋转，旋转不改变向量长度，符合正交矩阵的性质。\n",
    "\n",
    "#### 在 SVD 中的作用\n",
    "在 SVD 中，$U$ 和 $V$ 都是正交矩阵，分别对输入和输出空间进行旋转或反射。\n",
    "\n",
    "---\n",
    "\n",
    "### 2. 特征值与特征向量（Eigenvalue and Eigenvector）\n",
    "\n",
    "#### 定义\n",
    "对于一个方阵 $A$，如果存在一个非零向量 $v$ 和一个标量 $\\lambda$，使得：\n",
    "\n",
    "$$ A v = \\lambda v $$\n",
    "\n",
    "则：\n",
    "- $\\lambda$ 称为 $A$ 的特征值（eigenvalue）。\n",
    "- $v$ 称为 $A$ 的特征向量（eigenvector）。\n",
    "\n",
    "特征向量表示矩阵 $A$ 在某些方向上只进行缩放（不改变方向）的向量，特征值表示缩放的比例。\n",
    "\n",
    "#### 性质\n",
    "- 特征向量可以有多个，每个特征向量对应一个特征值。\n",
    "- 特征值可以是实数或复数，取决于矩阵 $A$ 的性质。\n",
    "- 如果 $A$ 是对称矩阵（见下文），其特征值是实数，且特征向量可以正交化。\n",
    "\n",
    "#### 简单案例\n",
    "考虑一个 2×2 矩阵：\n",
    "\n",
    "$$ A = \\begin{bmatrix} 4 & 0 \\\\ 0 & 2 \\end{bmatrix} $$\n",
    "\n",
    "求解特征值和特征向量：\n",
    "- 特征值通过求解特征方程 $\\det(A - \\lambda I) = 0$ 得到：\n",
    "  $$ \\det\\begin{bmatrix} 4 - \\lambda & 0 \\\\ 0 & 2 - \\lambda \\end{bmatrix} = (4 - \\lambda)(2 - \\lambda) = 0 $$\n",
    "  解得 $\\lambda_1 = 4$，$\\lambda_2 = 2$。\n",
    "- 对于 $\\lambda_1 = 4$，代入 $A - \\lambda I$ 求解 $v$：\n",
    "  $$ \\begin{bmatrix} 0 & 0 \\\\ 0 & -2 \\end{bmatrix} v = 0 \\quad \\Rightarrow \\quad v_1 = \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} $$\n",
    "- 对于 $\\lambda_2 = 2$：\n",
    "  $$ \\begin{bmatrix} 2 & 0 \\\\ 0 & 0 \\end{bmatrix} v = 0 \\quad \\Rightarrow \\quad v_2 = \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix} $$\n",
    "\n",
    "因此，特征值分别为 4 和 2，对应的特征向量为 $\\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix}$ 和 $\\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix}$。\n",
    "\n",
    "#### 在 SVD 中的作用\n",
    "在 SVD 中，特征值和特征向量的概念用于计算奇异值和奇异向量。SVD 的奇异值是通过对 $A^T A$ 或 $A A^T$ 的特征值取平方根得到的，特征向量则与奇异向量相关。\n",
    "\n",
    "---\n",
    "\n",
    "### 3. 对称矩阵（Symmetric Matrix）\n",
    "\n",
    "#### 定义\n",
    "对称矩阵是一个方阵 $A$，满足其转置矩阵等于自身，即：\n",
    "\n",
    "$$ A = A^T $$\n",
    "\n",
    "这意味着矩阵 $A$ 的元素关于主对角线对称：$a_{ij} = a_{ji}$。\n",
    "\n",
    "#### 性质\n",
    "- 对称矩阵的特征值都是实数。\n",
    "- 对称矩阵的特征向量可以选择为正交的（即可以构成正交矩阵）。\n",
    "- 对称矩阵可以通过特征值分解表示为 $A = Q \\Lambda Q^T$，其中 $Q$ 是正交矩阵，$\\Lambda$ 是特征值对角矩阵。\n",
    "\n",
    "#### 简单案例\n",
    "一个简单的对称矩阵：\n",
    "\n",
    "$$ A = \\begin{bmatrix} 5 & 2 \\\\ 2 & 3 \\end{bmatrix} $$\n",
    "\n",
    "验证其对称性：$A^T = \\begin{bmatrix} 5 & 2 \\\\ 2 & 3 \\end{bmatrix} = A$，满足对称矩阵定义。\n",
    "\n",
    "计算特征值：\n",
    "- 特征方程：$\\det(A - \\lambda I) = \\det\\begin{bmatrix} 5 - \\lambda & 2 \\\\ 2 & 3 - \\lambda \\end{bmatrix} = (5 - \\lambda)(3 - \\lambda) - 4 = \\lambda^2 - 8\\lambda + 11 = 0$\n",
    "- 解得 $\\lambda = \\frac{8 \\pm \\sqrt{64 - 44}}{2} = \\frac{8 \\pm \\sqrt{20}}{2} = 4 \\pm \\sqrt{5}$，均为实数。\n",
    "\n",
    "特征向量可以通过代入计算得到，且可以正交化。\n",
    "\n",
    "#### 在 SVD 中的作用\n",
    "在 SVD 中，我们构造 $A^T A$ 和 $A A^T$，这两个矩阵都是对称矩阵，因此可以进行特征值分解，进而求解奇异值和奇异向量。\n",
    "\n",
    "---\n",
    "\n",
    "### 4. 单位矩阵与矩阵分解的基础\n",
    "\n",
    "#### 单位矩阵（Identity Matrix）\n",
    "单位矩阵 $I$ 是一个对角线上全为 1，其余位置为 0 的方阵。例如，2×2 的单位矩阵为：\n",
    "\n",
    "$$ I = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} $$\n",
    "\n",
    "单位矩阵在矩阵运算中相当于数字中的 1，任何矩阵乘以单位矩阵结果不变。\n",
    "\n",
    "#### 矩阵分解\n",
    "矩阵分解是将一个矩阵表示为几个简单矩阵乘积的过程。常见的分解包括：\n",
    "- 特征值分解（适用于对称矩阵）：$A = Q \\Lambda Q^T$。\n",
    "- 奇异值分解（适用于任意矩阵）：$A = U \\Sigma V^T$。\n",
    "\n",
    "矩阵分解在降维、数据压缩和特征提取中非常重要。\n",
    "\n",
    "#### 简单案例\n",
    "对于对称矩阵 $A = \\begin{bmatrix} 4 & 0 \\\\ 0 & 2 \\end{bmatrix}$，其特征值分解为：\n",
    "\n",
    "$$ A = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\begin{bmatrix} 4 & 0 \\\\ 0 & 2 \\end{bmatrix} \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} $$\n",
    "\n",
    "这表明 $A$ 已经被分解为特征向量矩阵和特征值对角矩阵的乘积形式。\n",
    "\n",
    "#### 在 SVD 中的作用\n",
    "SVD 是一种更广义的矩阵分解方法，适用于非方阵，而特征值分解是 SVD 计算的基础步骤。\n",
    "\n",
    "---\n",
    "\n",
    "## 总结与联系\n",
    "\n",
    "- **正交矩阵**：列向量正交且单位化，在 SVD 中用于旋转或反射（$U$ 和 $V$）。\n",
    "- **特征值与特征向量**：描述矩阵在某些方向上的缩放特性，是计算奇异值的基础。\n",
    "- **对称矩阵**：具有实特征值和正交特征向量，SVD 通过构造 $A^T A$ 和 $A A^T$ 利用其性质。\n",
    "- **矩阵分解**：将复杂矩阵分解为简单矩阵乘积，是降维和数据分析的核心工具。\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "468e8a97",
   "metadata": {},
   "source": [
    "奇异值分解（SVD）的输入和输出：\n",
    "\n",
    "- **输入**：一个任意的矩阵 $A$，尺寸为 $m \\times n$（其中 $m$ 是行数，$n$ 是列数，可以是矩形矩阵，不必是方阵）。\n",
    "\n",
    "\n",
    "奇异值分解（SVD）得到的三个矩阵 $U$、$\\Sigma$ 和 $V^T$ 各有其特定的意义和用途，下面我简要说明它们的作用：\n",
    "\n",
    "1. **$U$（左奇异向量矩阵）**：\n",
    "   - 是一个 $m \\times m$ 的正交矩阵，列向量是矩阵 $A A^T$ 的特征向量。\n",
    "   - **作用**：表示原始矩阵 $A$ 在行空间（样本空间）中的主方向或基向量。简单来说，$U$ 的列向量描述了数据在行维度上的“模式”或“结构”。\n",
    "   - **应用**：在降维中，$U$ 的前几列可以用来投影数据到低维空间，保留主要信息（如在图像处理中提取主要特征）。\n",
    "\n",
    "2. **$\\Sigma$（奇异值矩阵）**：\n",
    "   - 是一个 $m \\times n$ 的对角矩阵，对角线上的值是奇异值（singular values），按降序排列，非负。\n",
    "   - **作用**：奇异值表示原始矩阵 $A$ 在每个主方向上的“重要性”或“能量”。较大的奇异值对应更重要的特征，较小的奇异值对应噪声或次要信息。\n",
    "   - **应用**：通过选择前 $k$ 个较大的奇异值，可以实现降维，丢弃不重要的信息（如数据压缩、去噪）。\n",
    "\n",
    "3. **$V^T$（右奇异向量矩阵的转置）**：\n",
    "   - 是 $V$ 的转置，$V$ 是一个 $n \\times n$ 的正交矩阵，列向量是矩阵 $A^T A$ 的特征向量。\n",
    "   - **作用**：表示原始矩阵 $A$ 在列空间（特征空间）中的主方向或基向量。简单来说，$V$ 的列向量描述了数据在列维度上的“模式”或“结构”。\n",
    "   - **应用**：类似 $U$，$V$ 的前几列可以用来投影数据到低维空间，提取主要特征。\n",
    "\n",
    "**整体作用**：\n",
    "- 结合起来，$A = U \\Sigma V^T$ 意味着原始矩阵 $A$ 可以被分解为一系列主方向（$U$ 和 $V$）和对应的权重（$\\Sigma$）的组合。这种分解揭示了数据的内在结构。\n",
    "- **主要应用**：\n",
    "  - **降维**：通过保留前 $k$ 个奇异值及其对应的 $U$ 和 $V$ 的列向量，可以近似重建 $A$，减少数据维度（如 PCA 的基础）。\n",
    "  - **数据压缩**：如图像压缩，丢弃小的奇异值以减少存储空间。\n",
    "  - **去噪**：小的奇异值往往对应噪声，丢弃它们可以提高数据质量。\n",
    "  - **推荐系统**：如矩阵分解，用于预测用户评分矩阵中的缺失值。\n",
    "\n",
    "简单来说，$U$、$\\Sigma$ 和 $V^T$ 提供了数据的核心结构信息，帮助我们在保留主要信息的同时简化数据处理。\n",
    "\n",
    "- **输出**：SVD 将矩阵 $A$ 分解为三个矩阵的乘积形式，即 $A = U \\Sigma V^T$，其中：\n",
    "  - $U$：一个 $m \\times m$ 的正交矩阵，列向量是 $A A^T$ 的特征向量，称为左奇异向量矩阵。\n",
    "  - $\\Sigma$：一个 $m \\times n$ 的对角矩阵，对角线上的元素是非负的奇异值（singular values），通常按降序排列，表示 $A$ 的“重要性”或“能量”。\n",
    "  - $V^T$：一个 $n \\times n$ 的正交矩阵的转置，$V$ 的列向量是 $A^T A$ 的特征向量，称为右奇异向量矩阵。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a535f4bd",
   "metadata": {},
   "source": [
    "# 奇异值的应用\n",
    "\n",
    "奇异值分解（SVD）后，原始矩阵 $A$ 被分解为 $A = U \\Sigma V^T$，这种分解是等价的，意味着通过 $U$、$\\Sigma$ 和 $V^T$ 的乘积可以完全重构原始矩阵 $A$，没有任何信息损失。\n",
    "\n",
    "但在实际应用中，我们通常不需要保留所有的奇异值和对应的向量，而是可以通过筛选规则选择排序靠前的奇异值及其对应的向量来实现降维或数据压缩。以下是这个过程的核心思想：\n",
    "\n",
    "1. **奇异值的排序**：\n",
    "   - 在 $\\Sigma$ 矩阵中，奇异值（对角线上的值）是按降序排列的。靠前的奇异值通常较大，代表了数据中最重要的信息或主要变化方向；靠后的奇异值较小，代表次要信息或噪声。\n",
    "   - 奇异值的大小反映了对应向量对原始矩阵 $A$ 的贡献程度。\n",
    "\n",
    "2. **筛选规则**：\n",
    "   - 我们可以根据需求选择保留前 $k$ 个奇异值（$k$ 是一个小于原始矩阵秩的数），并丢弃剩余的较小奇异值。\n",
    "   - 常见的筛选规则包括：\n",
    "     - **固定数量**：直接选择前 $k$ 个奇异值（例如，前 10 个）。\n",
    "     - **累计方差贡献率**：计算奇异值的平方（代表方差），选择累计方差贡献率达到某个阈值（如 95%）的前 $k$ 个奇异值。\n",
    "     - **奇异值下降幅度**：观察奇异值下降的“拐点”，在下降明显变缓的地方截断。\n",
    "\n",
    "3. **降维与近似**：\n",
    "   - 保留前 $k$ 个奇异值后，我们只取 $U$ 矩阵的前 $k$ 列（记为 $U_k$，尺寸为 $m \\times k$）、$\\Sigma$ 矩阵的前 $k$ 个奇异值（记为 $\\Sigma_k$，尺寸为 $k \\times k$）、以及 $V^T$ 矩阵的前 $k$ 行（记为 $V_k^T$，尺寸为 $k \\times n$）。\n",
    "   - 近似矩阵为 $A_k = U_k \\Sigma_k V_k^T$，这个矩阵是原始矩阵 $A$ 的低秩近似，保留了主要信息，丢弃了次要信息或噪声。\n",
    "   - 这种方法在降维（如主成分分析 PCA）、图像压缩、推荐系统等领域非常常用。\n",
    "\n",
    "4. **对应的向量**：\n",
    "   - $U$ 的列向量和 $V$ 的列向量分别对应左右奇异向量。保留前 $k$ 个奇异值时，$U_k$ 的列向量代表数据在行空间中的主要方向，$V_k$ 的列向量代表数据在列空间中的主要方向。\n",
    "   - 这些向量与奇异值一起，构成了数据的主要“模式”或“结构”。\n",
    "\n",
    "总结：SVD 分解后原始矩阵是等价的，但通过筛选排序靠前的奇异值和对应的向量，我们可以实现降维，保留数据的主要信息，同时减少计算量和噪声影响。这种方法是许多降维算法（如 PCA）和数据处理技术的基础。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cdb8cbd",
   "metadata": {},
   "source": [
    "# 实际案例"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9726783",
   "metadata": {},
   "source": [
    "\n",
    "**输出解释**：\n",
    "- 原始矩阵 $A$ 被分解为 $U$、$\\Sigma$（由 `sigma` 表示）和 $V^T$。\n",
    "- 通过 $U \\cdot \\Sigma \\cdot V^T$ 的矩阵乘法，可以完全重构原始矩阵 $A$，几乎没有信息损失（可能有非常小的数值误差）。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4474aa18",
   "metadata": {},
   "source": [
    "## 矩阵降维案例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b20bf485",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始矩阵 A:\n",
      "[[ 1  2  3]\n",
      " [ 4  5  6]\n",
      " [ 7  8  9]\n",
      " [10 11 12]\n",
      " [13 14 15]]\n",
      "\n",
      "奇异值 sigma:\n",
      "[3.51826483e+01 1.47690770e+00 9.86023090e-16]\n",
      "\n",
      "保留前 1 个奇异值后的近似矩阵 A_approx:\n",
      "[[ 1.85152908  2.05208851  2.25264793]\n",
      " [ 4.5411984   5.03310541  5.52501242]\n",
      " [ 7.23086771  8.01412231  8.7973769 ]\n",
      " [ 9.92053702 10.99513921 12.06974139]\n",
      " [12.61020633 13.9761561  15.34210588]]\n",
      "\n",
      "近似误差 (Frobenius 范数相对误差): 0.04194136031471535\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 创建一个矩阵 A (5x3)\n",
    "A = np.array([[1, 2, 3],\n",
    "              [4, 5, 6],\n",
    "              [7, 8, 9],\n",
    "              [10, 11, 12],\n",
    "              [13, 14, 15]])\n",
    "print(\"原始矩阵 A:\")\n",
    "print(A)\n",
    "\n",
    "# 进行 SVD 分解\n",
    "U, sigma, Vt = np.linalg.svd(A, full_matrices=False)\n",
    "print(\"\\n奇异值 sigma:\")\n",
    "print(sigma)\n",
    "\n",
    "# 保留前 k=1 个奇异值进行降维\n",
    "k = 1\n",
    "U_k = U[:, :k]  # 取 U 的前 k 列，因为要保持行数不变\n",
    "sigma_k = sigma[:k]  # 取前 k 个奇异值\n",
    "Vt_k = Vt[:k, :]  # 取 Vt 的前 k 行，因为要保持列数不变\n",
    "\n",
    "# 近似重构矩阵 A,常用于信号or图像筛除噪声\n",
    "A_approx = U_k @ np.diag(sigma_k) @ Vt_k\n",
    "print(\"\\n保留前\", k, \"个奇异值后的近似矩阵 A_approx:\")\n",
    "print(A_approx)\n",
    "\n",
    "# 计算近似误差\n",
    "error = np.linalg.norm(A - A_approx, 'fro') / np.linalg.norm(A, 'fro')\n",
    "print(\"\\n近似误差 (Frobenius 范数相对误差):\", error)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dafb9932",
   "metadata": {},
   "source": [
    "可以看到，再保留了k=1个奇异值后，近似误差仅为 4.19%，表明这种降维方式非常有效，丢失的信息很少。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0298d9e",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "---\n",
    "在机器学习中，如果对训练集进行 SVD 降维后训练模型，而测试集的特征数量与降维后的训练集不一致（测试集仍保持原始特征数量），该如何处理？\n",
    "### 1. 问题分析\n",
    "- **训练集降维**：假设训练集有 1000 个样本，50 个特征，通过 SVD 降维后保留 $k=10$ 个特征，得到形状为 `(1000, 10)` 的新数据。模型基于这 10 个特征进行训练。\n",
    "- **测试集问题**：测试集假设有 200 个样本，仍然是 50 个特征。如果直接输入测试集到模型中，特征数量不匹配（模型期望 10 个特征，测试集有 50 个），会导致错误。\n",
    "- **核心问题**：如何确保测试集也能被正确地降维到与训练集相同的 $k$ 个特征空间？\n",
    "\n",
    "---\n",
    "\n",
    "### 2. 解决方案：对测试集应用相同的变换\n",
    "在机器学习中，降维（如 SVD、PCA 等）是一种数据预处理步骤。训练集和测试集必须经过**相同的变换**，以确保数据分布一致。具体到 SVD，步骤如下：\n",
    "1. **训练阶段**：对训练集 $X_{train}$ 进行 SVD 分解，得到 $U$, $\\Sigma$, 和 $V^T$，并保存 $V^T$ 矩阵（或其前 $k$ 行）用于降维变换。\n",
    "2. **测试阶段**：使用从训练集得到的 $V^T$ 矩阵，将测试集 $X_{test}$ 投影到相同的低维空间，得到降维后的测试数据。\n",
    "3. **原因**：$V^T$ 矩阵定义了从原始特征空间到低维特征空间的映射关系，测试集必须使用相同的映射以保持一致性。\n",
    "\n",
    "数学上，假设训练集 SVD 分解为 $X_{train} = U \\Sigma V^T$，我们保留前 $k$ 个奇异值对应的 $V_k^T$（形状为 $k \\times 50$）。测试集降维公式为：\n",
    "$$X_{test\\_reduced} = X_{test} \\cdot V_k^T.T$$\n",
    "其中 $V_k^T.T$ 是 $V_k^T$ 的转置（形状为 $50 \\times k$），$X_{test}$ 是形状为 `(n_test, 50)` 的测试集矩阵，降维后 $X_{test\\_reduced}$ 的形状为 `(n_test, k)`。\n",
    "\n",
    "---\n",
    "\n",
    "### 3. 为什么不能对测试集单独做 SVD？\n",
    "- 如果对测试集单独进行 SVD，会得到不同的 $V^T$ 矩阵，导致测试集和训练集的低维空间不一致，模型无法正确处理测试数据。\n",
    "- 训练集的 $V^T$ 矩阵代表了训练数据的特征映射规则，测试集必须遵循相同的规则，否则会引入数据泄漏或不一致性问题。\n",
    "\n",
    "---\n",
    "\n",
    "### 4. 代码示例：训练集和测试集的 SVD 降维\n",
    "以下是一个完整的代码示例，展示如何对训练集进行 SVD 降维，训练模型，并对测试集应用相同的降维变换。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "70a4dc4e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "训练集形状: (800, 50)\n",
      "测试集形状: (200, 50)\n",
      "Vt_train 矩阵形状: (50, 50)\n",
      "保留 k=10 后的 Vt_k 矩阵形状: (10, 50)\n",
      "降维后训练集形状: (800, 10)\n",
      "降维后测试集形状: (200, 10)\n",
      "测试集准确率: 0.595\n",
      "训练集近似误差 (Frobenius 范数相对误差): 0.852479929511559\n"
     ]
    }
   ],
   "source": [
    "\n",
    "import numpy as np\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "# 设置随机种子以便结果可重复\n",
    "np.random.seed(42)\n",
    "\n",
    "# 模拟数据：1000 个样本，50 个特征\n",
    "n_samples = 1000\n",
    "n_features = 50\n",
    "X = np.random.randn(n_samples, n_features) * 10  # 随机生成特征数据\n",
    "y = (X[:, 0] + X[:, 1] > 0).astype(int)  # 模拟二分类标签\n",
    "\n",
    "# 划分训练集和测试集\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)\n",
    "print(f\"训练集形状: {X_train.shape}\")\n",
    "print(f\"测试集形状: {X_test.shape}\")\n",
    "\n",
    "# 对训练集进行 SVD 分解\n",
    "U_train, sigma_train, Vt_train = np.linalg.svd(X_train, full_matrices=False)\n",
    "print(f\"Vt_train 矩阵形状: {Vt_train.shape}\")\n",
    "\n",
    "# 选择保留的奇异值数量 k\n",
    "k = 10\n",
    "Vt_k = Vt_train[:k, :]  # 保留前 k 行，形状为 (k, 50)\n",
    "print(f\"保留 k={k} 后的 Vt_k 矩阵形状: {Vt_k.shape}\")\n",
    "\n",
    "# 降维训练集：X_train_reduced = X_train @ Vt_k.T\n",
    "X_train_reduced = X_train @ Vt_k.T\n",
    "print(f\"降维后训练集形状: {X_train_reduced.shape}\")\n",
    "\n",
    "# 使用相同的 Vt_k 对测试集进行降维：X_test_reduced = X_test @ Vt_k.T\n",
    "X_test_reduced = X_test @ Vt_k.T\n",
    "print(f\"降维后测试集形状: {X_test_reduced.shape}\")\n",
    "\n",
    "# 训练模型（以逻辑回归为例）\n",
    "model = LogisticRegression(random_state=42)\n",
    "model.fit(X_train_reduced, y_train)\n",
    "\n",
    "# 预测并评估\n",
    "y_pred = model.predict(X_test_reduced)\n",
    "accuracy = accuracy_score(y_test, y_pred)\n",
    "print(f\"测试集准确率: {accuracy}\")\n",
    "\n",
    "# 计算训练集的近似误差（可选，仅用于评估降维效果）\n",
    "X_train_approx = U_train[:, :k] @ np.diag(sigma_train[:k]) @ Vt_k\n",
    "error = np.linalg.norm(X_train - X_train_approx, 'fro') / np.linalg.norm(X_train, 'fro')\n",
    "print(f\"训练集近似误差 (Frobenius 范数相对误差): {error}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd5308e1",
   "metadata": {},
   "source": [
    "### 6. 实际操作中的注意事项\n",
    "1. **标准化数据**：在进行 SVD 之前，通常需要对数据进行标准化（均值为 0，方差为 1），以避免某些特征的量纲差异对降维结果的影响。可以使用 `sklearn.preprocessing.StandardScaler`。\n",
    "   ```python\n",
    "   from sklearn.preprocessing import StandardScaler\n",
    "   scaler = StandardScaler()\n",
    "   X_train_scaled = scaler.fit_transform(X_train)\n",
    "   X_test_scaled = scaler.transform(X_test)\n",
    "   ```\n",
    "   注意：`scaler` 必须在训练集上 `fit`，然后对测试集只用 `transform`，以避免数据泄漏。\n",
    "\n",
    "2. **选择合适的 $k$**：可以通过累计方差贡献率（explained variance ratio）选择 $k$，通常选择解释 90%-95% 方差的 $k$ 值。代码中可以计算：\n",
    "   ```python\n",
    "   explained_variance_ratio = np.cumsum(sigma_train**2) / np.sum(sigma_train**2)\n",
    "   print(f\"前 {k} 个奇异值的累计方差贡献率: {explained_variance_ratio[k-1]}\")\n",
    "   ```\n",
    "\n",
    "3. **使用 sklearn 的 TruncatedSVD**：`sklearn` 提供了 `TruncatedSVD` 类，专门用于高效降维，尤其适合大规模数据。它直接计算前 $k$ 个奇异值和向量，避免完整 SVD 的计算开销。\n",
    "   ```python\n",
    "   from sklearn.decomposition import TruncatedSVD\n",
    "   svd = TruncatedSVD(n_components=k, random_state=42)\n",
    "   X_train_reduced = svd.fit_transform(X_train)\n",
    "   X_test_reduced = svd.transform(X_test)\n",
    "   print(f\"累计方差贡献率: {sum(svd.explained_variance_ratio_)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acb6f5ea",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "vs",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
